Pisano Periods#6390

Pisano Periods

1 second

122.174 megabytes

Easy

In 1960, Donald Wall of IBM, in White Plains, NY, proved that the series obtained by taking each element of the Fibonacci series modulo $m$ was periodic.

For example, the first ten elements of the Fibonacci sequence, as well as their remainders modulo $11$ , are:

The sequence made up of the remainders then repeats. Let $k (m)$ be the length of the repeating subsequence; in this example, we see $k (11) = 10$ k(11) = 10.

Wall proved several other properties, some of which you may find interesting:

If $m > 2$ m > 2, $k (m)$ is even.
For any even integer $n > 2$ n > 2, there exists $m$ such that $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
If $n > 2$ n > 2, $k (10 n) = 15 \cdot 1 0^{n - 1}$ k(10n) = 15 \cdot 10^{n-1}

For this problem, you must write a program that calculates the length of the repeating subsequence $k (m)$ for different modulo values $m$ .

Input

The first line contains the number of data sets $p$ ( $1 \leq p \leq 1000$ 1 \le p \le 1000) that follow. Each data set is a single line that consists of two space separated integer values $n$ and $m$ , where $n$ is the data set number and $m$ ( $2 \leq m \leq 1000000$ 2 \le m \le 1000000) is the modulo value.

Output

For each data set there is one line of output. It contains the data set number $n$ followed by a single space, followed by the length of the repeating subsequence for $m$ - the value of $k (m)$ .

Examples

Example 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