SPOJ in Gyumri

  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.

   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) ≤ m2 − 1
• k(2n) = 3 ∗ 2n−1
• k(5n) = 4 ∗ 5n
• k(2 ∗ 5n) = 6n
• If n > 2, k(10n) = 15 ∗ 10n−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 of input contains a single integer P , (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set is a single line that consists of two space separated integer values N and M .

   N is the data set number. M is the modulo value (2 ≤ M ≤ 1, 000, 000).

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 , k(M ).

Examples