斐波那契数列由以下递推关系定义：

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