eolymp
Задачи

Период Пизано

Период Пизано

В 1960 году Дональд Уолл из IBM, Phite Plains, Нью-Йорк, доказал, что множество чисел Фибоначчи, взятое по модулю m, является периодичным.

Рассмотрим первые десять чисел Фибоначчи, и их остатки при делении на 11:

n|12345678910
F(n)|11235813213455
F(n) mod 11|11235821010

Последовательность остатков повторяется. Пусть k(m) - длина повторяющейся подпоследовательности, тогда k(11) = 10.

Уолл доказал несколько свойств, некоторые из которых будут Вам интересны:

  • Если m > 2, то k(m) четно.
  • Для любого четного n > 2 существует такое m, что k(m) = n.
  • k(m)m2 - 1
  • k(2n) 3 * 2(n-1)
  • k(5n) = 4 * 5n
  • k(2 * 5n) = 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).

Лимит времени 1 секунда
Лимит использования памяти 122.17 MiB
Входные данные #1
5
1 4
2 5
3 11
4 123456
5 987654
Выходные данные #1
1 6
2 20
3 10
4 15456
5 332808
Источник 2013 ACM Greater New York Region, Октябрь 27, Задача D