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