Rikka with Rock-paper-scissors

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

Sample Input

5

1 998244353

2 998244353

3 998244353

4 998244353

5 998244353

Sample Output

6

90

972

9720

89910

Source

2017 Multi-University Training Contest - Team 5

https://acm.hdu.edu.cn/showproblem.php?pid=6088