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