#### Registered Users Only

Please login to view and utilize this feature.

A more fun version of a simpler question... :)

Each input file consists of *T* test cases, where each test case follows the following format:

You are given two natural numbers *N* and *M*. Write a program that outputs the remainder of the *N*^{th} Fibonacci number when divided by *M*.

For those who were sleeping during lesson, the Fibonacci sequence is generated as follows:

*f*_{0} = 0

*f*_{1} = 1

*f _{i}* =

*f*

_{i-1}+

*f*

_{i-2}for

*i*≥ 2

You are supposed to output an integer *f _{N}* (mod

*M*).

## Input

The first line of the input contains one integer *T* (1 ≤ *T* ≤ 100000)

The next *T* lines of the output contain two integers each, *N* and *M* (1 ≤ *N*, *M* ≤ 1,000,000,000).

## Output

For each of the *T* test cases, output the integer *f _{N}* (mod

*M*).

## Sample Input 1

1 3 1337

## Sample Output 1

2

## Sample Input 2

3 3 1337 10 1337 10 54

## Sample Output 2

2 55 1

## Explanation for Sample Output 1

*f*

_{2}=

*f*

_{1}+

*f*

_{0}= 1 + 0 = 1

*f*

_{3}=

*f*

_{2}+

*f*

_{1}= 1 + 1 = 2.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 0 | 0 | 1s | 32MB | Average |

2 | 100 | 20 | 1s | 32MB | Average |

### Judge Compile Command

g++ ans.cpp -o fibo_ex -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512