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 n^th fibonacci number is divided by k?

Help Brain, solving this mystery.

Statement : Given n and k, find the remainder when the n^th fibonacci number is divided by k.
Constraints :
1 <= n <= 10⁴
1 < k <= 10⁵

n^th fibonnaci numbers are defined by :

fib_n = 1                        if n = 1 or n = 2
      = fib_n-1 + fib_n-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