Это не может продолжаться вечно
"Давным-давно в далекой-далекой галактике...". На самом деле, так давно, что Империи еще не существовало, и были планеты без космических путешествий. В одном из таких отдаленных миров обитали существа, называемые тайесы, которые размножались почкованием. Как только тайес отделялся от родителя, ему требовалась одна единица времени, чтобы достичь зрелости и начать размножаться, что совпадало с временем, необходимым для роста и отделения новой почки от родителя. Тайесы живут чрезвычайно долго, поэтому стало важно выяснить, сколько их может быть у кого-то, если в момент времени ноль у человека не было тайеса, а в момент времени один он получил незрелого тайеса, только что отпочковавшегося от зрелого тайеса, принадлежащего другу.
Это приводит к следующей рекуррентной формуле: 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 при этом модуле.