Період Пізано#6390

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

1 секунда

122,174 мегабайта

Легка

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

Розглянемо перші десять чисел Фібоначчі та їх залишки при діленні на $11$ :

Послідовність залишків повторюється. Нехай $k (m)$ - це довжина повторюваної підпослідовності, тоді $k (11) = 10$ k(11) = 10.

Уолл довів кілька властивостей, які можуть бути вам цікавими:

Якщо $m > 2$ m > 2, то $k (m)$ парне.
Для будь-якого парного $n > 2$ n > 2 існує таке $m$ , що $k (m) = n$ k(m) = n.
$k (m) \leq m^{2} - 1$ k(m) \le m^2 - 1
$k (2^{n}) \leq 3 \cdot 2^{n - 1}$ k(2^n) \le 3 \cdot 2^{n-1}
$k (5^{n}) = 4 \cdot 5^{n}$ k(5^n) = 4 \cdot 5^n
$k (2 \cdot 5^{n}) = 6 n$ k(2 \cdot 5^n) = 6n
Якщо $n > 2$ n > 2, то $k (10 n) = 15 \cdot 1 0^{n - 1}$ k(10n) = 15 \cdot 10^{n-1}

Напишіть програму, яка обчислить довжину повторюваної підпослідовності $k (m)$ для різних значень модуля $m$ .

Вхідні дані

Перший рядок містить кількість тестів $p$ ( $1 \leq p \leq 1000$ 1 \le p \le 1000). Дані кожного тесту розташовані в одному рядку і містять два цілі числа $n$ і $m$ , де $n$ — номер тесту, а $m$ ( $2 \leq m \leq 1000000$ 2 \le m \le 1000000) — значення модуля.

Вихідні дані

Для кожного тесту виведіть в окремому рядку номер тесту $n$ , пробіл, і довжину повторюваної підпослідовності для $m$ — значення $k (m)$ .

Приклади

Приклад 1

Loading

k (11) = 10

m > 2

n > 2

k (m) = n

k (m) \leq m^{2} - 1

k (2^{n}) \leq 3 \cdot 2^{n - 1}

k (5^{n}) = 4 \cdot 5^{n}

k (2 \cdot 5^{n}) = 6 n

n > 2

k (10 n) = 15 \cdot 1 0^{n - 1}

1 \leq p \leq 1000

2 \leq m \leq 1000000