FIBPARIT - Fibonnaci Parity

no tags 

In the quest to take over the world, the Pinky falls from the table, upside down. Miracle!!! Now he is intelligent. and the conversation goes like:

Brains : Pinky, are you pondering what I'm pondering?
Pinky : I think so, what would be the remainder when the nth fibonacci number is divided by k?

Help Brain, solving this mystery.

Statement : Given n and k, find the remainder when the nth fibonacci number is divided by k.
Constraints :
1 <= n <= 104
1 < k <= 105

nth fibonnaci numbers are defined by :

fibn = 1                        if n = 1 or n = 2
      = fibn-1 + fibn-2        for n > 2

Fibonacci series goes like : 1 1 2 3 5 8 13...

Input

The first line contains t, number of test cases. In following t lines, there are two space separated numbers, n k.

Output

For each test cases, print the solution to the Pinky's quest in new line.

Example

Input:
5
5 2
4 3
10 4
4 5
11 12

Output:
1
0
3
3
5

hide comments
[Lakshman]: 2013-08-16 09:55:29

@Balo ans=66875

Anubhav Balodhi : 2013-08-07 16:44:42

is the answer for (n,m)=(10000,100000) 70043 ?!?

s.malarvizhi: 2013-07-07 10:57:54

i got WA.anyone plz help me and provide some more testcases.


Added by:abhiranjan
Date:2010-11-19
Time limit:0.307s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All