Pisano Period

In 1960, Donald Wall, who worked at IBM, proved that the remainders of the Fibonacci numbers modulo $m$ form a repeating cycle.

For example, the first 10 Fibonacci numbers and their remainders modulo 11 are shown below.

The sequence of remainders repeats the same block over and over. Writing $k(m)$ for the length of that repeating block, $k(11) = 10$.

Wall proved several other properties.

• $k(m)$ is even whenever $m > 2$.
• For every even integer $n$ greater than $2$ there is an $m$ with $k(m) = n$.
• $k(m) \le m^2 - 1$
• $k(2^n) = 3 \times 2^{n-1}$
• $k(5^n) = 4 \times 5^n$
• $k(2 \times 5^n) = 12 \times 5^n$
• $k(10^n) = 15 \times 10^{n-1}$ when $n > 2$

Given $m$, write a program that computes $k(m)$.

The first line contains the number of test cases $P$.

Each of the next $P$ lines contains two integers $N$ and $M$ separated by a single space. $N$ is the number of the test case and $M$ is the $m$ described above.

For each test case, print the test case number $N$ and $k(M)$ on one line, separated by a single space. Keep the order in which the test cases were given.

• $1 \le P \le 1{,}000$
• $2 \le M \le 1{,}000{,}000$
• The sum of $k(M)$ over all test cases is at most $500{,}000$.