В \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)}.