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