After solving Fib-Factorization and ModFib-Period, you would probably be interested by solving this new task:
Simply compute Fib(N) mod Fib(K), where Fib(N) denotes the Nth term of the Fibonacci sequence.
(If N<2 Fib(N)=N, else Fib(N)=Fib(N-1)+F(N-2)).

Input

The input begins with the number T of test cases in a single line.
In each of the next T lines there are two integers N, K.

Output

For each test case, on a single line, print Fib(N) mod Fib(K).

Example

Input:
2
5 5
13 5
Output:
0
3

Constraints

1 < T < 10^5
1 < N < 10^18
1 < K <= 10^3

Edit(2017-02-11) : New time limit (after compiler changes).