What a sequence!

Time limit2sMemory limit512 MB

Summary

For each of up to a million queries, compute a_p mod p where a is defined by a_{n+2} = k a_{n+1} + a_n with a_0 = 0, a_1 = 1, given an odd prime p and k in {1,3,5,7}.

Level: Medium7 of 10
Topics: Math, Number theory, Matrix, Implementation
Solved: No attempts yet

Problem

The sequence $a_{n}$ is defined by the recurrence

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

Given $k \in \{1,3,5,7\}$ and an odd prime $p$ , find the value of $a_{p} \bmod{p}$ .

Input

The first line contains one integer $Z \le 10^6$ , the number of test cases.

Each test case consists of a single line with two natural numbers $p$ and $k$ , where $p$ is an odd prime.

Output

For each test case, print one line with the value of $a_{p} \bmod{p}$ .

Constraints

$k \in \{1,3,5,7\}$
The total number of digits of $p$ over all test cases does not exceed $10^{6}$ .

Examples1

Example 1
Input
```
3
3 5
11 1
13 3
```
Expected output
```
2
1
0
```