问题描述

在一个遥远的王国里，睿智的国王-对数字有着特殊的兴趣。有一天，他发现了一个神秘的序列，他认为这个序列蕴含着宇宙的秘密。我们将这个序列称为“国王的序列”，它的定义如下：

• 序列以 $f(0) = 0$ 和 $f(1) = 1$ 开始。
• 对于每个整数 $i \geq 0$，下一个序列中的数字计算为 $f(i+2) = f(i+1) + f(i)$。

国王想考验他的臣民的数学能力，于是他提出了一个挑战。他要求他们在给定两个非负整数 $a$ 和 $b$ 以及一个正整数 $n$ 的情况下，找出 $f(a^b)$ 除以 $n$ 的余数。

然而，国王也警告他们，随着数字的增长，计算会变得越来越困难。他承诺对任何能解决这个难题的人给予丰厚的奖励。

你能接受国王的挑战，帮助他揭开宇宙的秘密吗？

输入格式

先输入一个整数 $t(t<100)$ 表示测试数据组数。

接下来每行三个整数 $a,b,n$。

输出格式

对于每组输入，输出一行一个整数，表示 $f(a^b)\mod n$。

样例

2
1000 213314 500
2 3 10

375
1

数据范围

• 对于 $100\%$ 的数据：$0≤a,b<2^{64}$，$1≤n≤1000$。