Це не може тривати вічно
"Давно-давно в далекій-далекій галактиці...", так давно, що Імперії ще не існувало, і були планети без космічних подорожей. У віддаленому куточку була планета, де найпоширенішими домашніми улюбленцями були істоти, звані таї, які розмножувалися брунькуванням. Коли тая відділялася від свого батька, їй потрібна була одна одиниця часу, щоб дозріти до стану розмноження, що, випадково, було тривалістю часу, необхідною для вирощування нової бруньки та її відділення від батька. Таї живуть дуже довго, тому стало важливо дослідити, скільки їх може бути у когось, припускаючи, що в момент часу нуль у людини не було таї, а в момент часу один вона отримала незрілу таю, щойно відокремлену від зрілої таї, що належала другу.
Це призводить до наступної рекурентної формули: T(0) = 0, T(1) = 1, T(n) = T(n - 1) + T(n - 2), для n > 1.
Обчислення на той час включали беззнакові двійкові числа з 24 бітами. Це мотивувало особливо допитливого жителя, Леона, дослідити ряд, згенерований цією рекурентною формулою, але обмежений модулем - і не лише модулем 2^24, що нав'язаний обчислювальним обладнанням. Отже, питання полягає в тому, наскільки довгий ряд чисел генерується цією рекурентною формулою, підлягаючи арифметиці з певним модулем, перш ніж він почне повторюватися. Ось перші кілька рядів:
Завдання полягає в тому, щоб визначити довжину періоду для кожного модуля, заданого у вхідному файлі, і повідомити про це.
Вхідні дані
Вхідний файл містить невизначену кількість рядків, кожен з яких містить одне ціле число mod, гарантовано в діапазоні 2 ≤ mod ≤ 16777216 (2^24). Останній рядок містить '0' як кінець даних і не повинен оброблятися.
Вихідні дані
Для кожного модуля у вхідному файлі надрукуйте модуль, один пробіл, а потім розмір найменшого періоду цих чисел T за цим модулем.