Bu Belə Davam Edə Bilməz

"

textitÇox-çox uzaq bir qalaktikada, çox-çox uzun zaman əvvəl..". O qədər uzun zaman əvvəl ki, İmperiya hələ mövcud deyildi və bəzi planetlərdə kosmik səyahət belə yox idi. Uzaq bir küncdə, tayes adlanan üstünlük təşkil edən ev heyvanının tumurcuqlanma yolu ilə çoxaldığı bir dünya var idi. Taye valideynindən ayrıldıqdan sonra, yetişib çoxalma nöqtəsinə çatmaq üçün bir zaman vahidi tələb olunurdu ki, bu da təsadüfən yeni bir tumurcuğun böyüyüb valideynindən ayrılması üçün lazım olan vaxtın uzunluğuna bərabər idi. Tayeslər çox uzun ömürlüdürlər, buna görə də, sıfır zamanında bir taye olmayan, bir zamanında isə dostunun yetkin tayeindən təzə tumurcuqlanmış bir yetkin olmayan taye əldə edən birinin neçə taye ola biləcəyini araşdırmaq vacib oldu.

Bu, aşağıdakı təkrarlama ilə nəticələnir:

textbfT(0) = 0,

textbfT(1) = 1,

textbfT(n) = T(n - 1) + T(n - 2),

textbfn 003e

textbf1 üçün.

O vaxt hesablamalar

textbf24 bitlik işarəsiz ikili ədədlərlə aparılırdı. Bu, xüsusilə maraqlı bir sakin olan Leonu, bu təkrarlama ilə yaradılan seriyanı, lakin yalnız hesablama avadanlığı tərəfindən məcbur edilən

textbf2^24 modulu ilə məhdudlaşdırılmadan, müəyyən bir modullarla məhdudlaşdıraraq araşdırmağa təşviq etdi. Beləliklə, sual bu təkrarlama ilə yaradılan ədədlərin seriyasının, müəyyən bir modulla arifmetikaya tabe olaraq, təkrarlamağa başlamazdan əvvəl nə qədər uzun olduğunu müəyyən etmək olur. Budur, ilk bir neçə seriya:

includegraphicshttps://static.e-olymp.com/content/fb/fbd9016555ffa96fc650756a62da0528459fd1ce.jpg

Problem, giriş faylında verilmiş hər bir modul üçün dövrün uzunluğunu müəyyən etmək və onu hesabat etməkdir.

InputFile

Giriş faylı, hər biri

textbf2 ≤

textbfmod ≤

textbf16777216 (2^24) aralığında olan bir tam ədəd modunu ehtiva edən qeyri-müəyyən sayda sətir ehtiva edir. Son sətir '

textbf0' ilə bitir və işlənməməlidir.

OutputFile

Giriş faylındakı hər bir modul üçün modulu, bir boşluq və sonra həmin modul altında bu

textbfT ədədlərinin ən kiçik dövrünün ölçüsünü çap edin.