시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 512 MB222100.000%

문제

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

예제 입력 1

3
3 5
11 1
13 3

예제 출력 1

2
1
0