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