이런 수열이!

시간 제한2초메모리 제한512 MB

요약

홀수 소수 p와 k∈{1,3,5,7}이 주어질 때, a_{n+2}=k·a_{n+1}+a_n, a_0=0, a_1=1로 정의된 수열의 a_p mod p 값을 최대 백만 개의 질의에 대해 구한다.

문제

수열 $a_{n}$ 이 다음과 같은 점화식으로 정의된다.

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

$k \in \{1,3,5,7\}$ 와 홀수인 소수 $p$ 가 주어질 때, $a_{p} \bmod{p}$ 의 값을 구하여라.

첫째 줄에 테스트 케이스의 수 $Z \le 10^6$ 가 주어진다.

각 테스트 케이스마다 한 줄에 자연수 $p$ 와 $k$ 가 주어진다. $p$ 는 홀수인 소수이다.

각 테스트 케이스마다 $a_{p} \bmod{p}$ 의 값을 한 줄에 하나씩 출력한다.