Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0069 - PISANO PERIODS

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:

 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) mod 11 | 1 1 2 3 5 8 2 10 1 0

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 2n1
• k(5n) = 4 5n
• k(2 5n) = 6n
• If n > 2, k(10n) = 15 10n1

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

 № stdin stdout 1 5 1 4 2 5 3 11 4 123456 5 987654 1 6 2 20 3 10 4 15456 5 332808

 Ավելացրեց. Հրանտ Հովհաննիսյան Ամսաթիվ. 2014-01-05 Ժամանակի սահմանափակումը. 1s Ծրագրի տեքստի սահմանափակումը. 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Լեզուներ. Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE Աղբյուրը. NA Greater New York 2013.D