23466번 - What a sequence! 다국어

문제

Let $a_{n}$ be a sequence defined by the recursive formula:

$$\begin{align*} a_{n+2} &= k\cdot a_{n+1} + a_{n} \\ a_{0} &= 0 \\ a_{1} &= 1 \end{align*}$$

Given a certain $k \in \{1,3,5,7\}$ and an odd prime number $p,ドル your task is to find the value of $a_{p} \bmod{p}$.

입력

In the first line one integer $Z \le 10^6$ is given, denoting number of testcases described in following lines.

For each test case, first and the only input line contains two natural numbers $p$ and $k,ドル $p$ being an odd prime number.

출력

For each test case you should print exactly one line containing the value of $a_{p} \bmod{p}$.

제한

• $k \in \{1,3,5,7\}$
• The total length of the numbers $p$ in the all testcases doesn't exceed 10ドル^{6}$.

힌트