Pisano Periods
In 1960, Donald Wall of IBM, in Phite Plains, NY, proved that the series obtained by taking each element of the Fibonacci series modulo m was periodic.
For example, the first ten element 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.
Wall proved several other properties, some of which you may find interesting:
If m > 2, k(m) is even.
For any even integer n > 2, there exists m such that k(m) = n.
k(m) ≤ m^2 - 1
k(2^n) ≤ 3 * 2^{(n-1)}
k(5^n) = 4 * 5^n
k(2 * 5^n) = 6n
If n > 2, k(10n) = 15 * 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 set p (1 ≤ p ≤ 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 ≤ m ≤ 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).