Pisano Period | cho.sh

Problem

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.

$n$	1	2	3	4	5	6	7	8	9	10
$F(n)$	1	1	2	3	5	8	13	21	34	55
$F(n) \bmod 11$	1	1	2	3	5	8	2	10	1	0

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)$ .

Input

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.

Output

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.

Constraints

$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$ .