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

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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.