题目描述

我不是音游人，不会KPS的计算方式，这里只是引用KPS的概念（

灰灰又打开了他钟爱的冰与火之舞！这已经是他在steam上玩冰与火的第114514个小时了。
因为单身了16年，灰灰的手速现在已经快到离谱，他经常在MPT管理群里炫耀他的KPS(Keys Per Second)。
今天灰灰又跳出来炫耀手速。他给出了一个公式：\(KPS = A^B\ mod\ P\)
\(A\)为单身年数，\(B\)为牛牛长度（？），\(P\)为游玩小时数。
听灰灰这样说之后，MPT群里群里的每一个人都想试试计算出自己的KPS。请你帮帮MPT大佬计算他们的KPS。

输入格式

第一行一个整数\(M\)，表示数据组数。
接下来的\(M\)行，每行三个整数，分别为\(A, B, P\)

输出格式

对于从第二行开始的每组数据，输出一个整数为该组的计算结果。

样例

输入

3 
2 10 9
3 6 29
3 1 3

输出

7
4
0

数据规模与约定

对于\(100%\)的数据，保证\(0 \leqslant a, b < 2^31, a + b > 0, 2 \leqslant p < 2^31, 0 < m \leqslant 10\)