Let's define:
F(0)=0, F(1)=1.
F(j)=F(j-1)+F(j-2), for j>1

P(0)=0, P(1)=1, P(2)=2
P(j)=P(j-1)+2P(j-3), for j>2
Given an integer X and M, calculate the remainder of F(X) and P(X) after dividing them by the modulus M.

Input

First line: positive integer T - numer of test cases, T<20000.
Next T lines contain 2 integers each: X_i, and M_i.
Data constraints:
0 < X_i < +2⁶⁰
2 < M_i < +2³⁰

Output

For each of test cases, output the numbers F(X_i) mod M_i and P(X_i) mod M_i separated by a single space - one line per test case.

Example

Input:
6
1 23
4 56
7 89
123 456
7890 123
123456789012 34567890


Output:
1 1
3 4
13 20
2 204
55 103
29441184 24923102