给定 n 组询问，每组询问给定整数 a,b,p，计算 C^a_b \pmod {p} 的值。
保证 p 是质数。
输入
多组询问，第一行一个整数 n \ (1 \leq n \leq 20)。
接下来 n 行，每行两个整数 a,b,p \ (1 \leq b \leq a \leq 10^{18},1 \leq p \leq 10^5)。
输出
输出 n 行，每行输出一个询问的解。
样例
| 标准输入 复制文本 |
3 5 3 7 3 1 5 6 4 13 |
| 标准输出 复制文本 |
3 3 2 |