Задачи
Период Пизано
Период Пизано
В \textbf{1960} году Дональд Уолл из IBM, Phite Plains, Нью-Йорк, доказал, что множество чисел Фибоначчи, взятое по модулю \textbf{m}, является периодичным.
Рассмотрим первые десять чисел Фибоначчи, и их остатки при делении на \textbf{11}:
Последовательность остатков повторяется. Пусть \textbf{k(m)} - длина повторяющейся подпоследовательности, тогда \textbf{k(11)} = \textbf{10}.
Уолл доказал несколько свойств, некоторые из которых будут Вам интересны:
\begin{itemize}
\item Если \textbf{m }> \textbf{2}, то \textbf{k(m)} четно.
\item Для любого четного \textbf{n }> \textbf{2} существует такое \textbf{m}, что \textbf{k(m)} = \textbf{n}.
\item \textbf{k(m)} ≤ \textbf{m^2 - 1}
\item \textbf{k(2^n) }≤\textbf{ 3 * 2^\{(n-1)\}}
\item \textbf{k(5^n) = 4 * 5^n}
\item \textbf{k(2 * 5^n)} = \textbf{6n}
\item Если \textbf{n} > \textbf{2}, то \textbf{k(10n)} = \textbf{15 * 10^\{(n-1)\}}
\end{itemize}
Напишите программу, которая вычислит длину повторяющейся подпоследовательности \textbf{k(m)} для различных значений модуля \textbf{m}.
\InputFile
Первая строка содержит количество тестов \textbf{p }(\textbf{1 }≤ \textbf{p }≤ \textbf{1000}). Данные каждого теста расположены на одной строке и содержат два целых числа \textbf{n }и \textbf{m}, где \textbf{n }- номер теста, а \textbf{m }(\textbf{2 }≤ \textbf{m }≤ \textbf{1000000}) - значение модуля.
\OutputFile
Для каждого теста вывести в отдельной строке номер теста \textbf{n}, пробел, и длину повторяющейся подпоследовательности для \textbf{m} - значение \textbf{k(m)}.
Входные данные #1
5 1 4 2 5 3 11 4 123456 5 987654
Выходные данные #1
1 6 2 20 3 10 4 15456 5 332808