Best Solver

Time Limit: 1500/1000 MS (Java/Others)

Memory Limit: 65535/102400 K (Java/Others)

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$.

Sample Input

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

Sample Output

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

Hint

wange2014

Source

2015 ACM/ICPC Asia Regional Shenyang Online

提交代码