Problem Description

The so-called best problem solver can easily solve this problem, with his/her childhood sweetheart.

It is known that $y = (5+2\sqrt{6})^{1+2^x}$.
For a given integer $x~(0\le x<2^{32})$ and a given prime number $M~(M\le 46337)$, print $[y]\%M$. ($[y]$ means the integer part of $y$)

Input

An integer $T~(1<T\le 1000)$, indicating there are $T$ test cases.
Following are $T$ lines, each containing two integers $x$ and $M$, as introduced above.

Output

The output contains exactly $T$ lines.
Each line contains an integer representing $[y]\%M$.

7
0 46337
1 46337
3 46337
1 46337
21 46337
321 46337
4321 46337

Case #1: 97
Case #2: 969
Case #3: 16537
Case #4: 969
Case #5: 40453
Case #6: 10211
Case #7: 17947