피보나치 수열은 다음 점화식으로 정의됩니다.

$$F_n=F_{n-1}+F_{n-2}.$$

초깃값은 $F_0=0$과 $F_1=1$입니다.

피보나치 수열의 처음 몇 항은 $0,1,1,2,3,5,8,13,21,\ldots$입니다.

다음과 같이 정의합니다.

• $G(1,n)$은 $n$번째 피보나치 수를 나타냅니다.

• $G(2,n)=G(1,G(1,n))$,

• $G(i,n)=G(1,G(i-1,n))$.

$G(k,n)\bmod p$를 계산하세요.

입력

입력의 첫 번째 줄에는 테스트 케이스의 수인 정수 $T$ 하나가 주어집니다 ($1\le T\le10^5$).

각 테스트 케이스는 한 줄로 이루어지며, 정수 $n$, $k$, $p$ 세 개가 한 칸의 공백으로 구분되어 주어집니다 ($1\le k,n\le10^{18}$, $1\le p\le10^6$).

출력

각 테스트 케이스마다 $G(k,n)\bmod p$를 한 줄에 출력하세요.

예제

입력 1

10
1 1 1000000
1 2 1000000
1 3 1000000
2 1 1000000
2 2 1000000
2 3 1000000
3 1 1000000
3 2 1000000
3 3 1000000
1000000000000000000 1000000000000000000 1000000

출력 1

1
1
1
1
1
1
2
1
1
890625