Problem Description

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

Alice and Bob are going to play a famous game: Rock-paper-scissors. Both of them don’t like to think a lot, so both of them will use the random strategy: choose rock/paper/scissors in equal probability.

They want to play this game $n$ times, then they will calculate the score $s$ in the following way: if Alice wins $a$ times, Bob wins $b$ times, and in the remaining $n-a-b$ games they make a tie, the score will be the greatest common divisor of $a$ and $b$.

Know Yuta wants to know the expected value of $s \times 3^{2n}$. It is easy to find that the answer must be an integer.

It is too difficult for Rikka. Can you help her?

Note: If one of $a,b$ is $0$, we define the greatest common divisor of $a$ and $b$ as $a+b$.

Input

The first line contains a number $t(1 \leq t \leq 20)$, the number of the testcases. There are no more than $2$ testcases with $n \geq 10^4$.

For each testcase, the first line contains two numbers $n,mo(1 \leq n \leq 10^5, 10^8 \leq mo \leq 10^9)$

It is guaranteed that $mo$ is a prime number.

Output

For each testcase, print a single line with a single number -- the answer modulo $mo$.

5
1 998244353
2 998244353
3 998244353
4 998244353
5 998244353

6
90
972
9720
89910