Період Пізано
У 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).