5359 - 组合数学:求组合数(模版3)

通过次数

18

提交次数

82

Time Limit : 1 秒
Memory Limit : 128 MB

给定n组询问,每组询问给定的2个整数a,b, 请你输出C_a^b mod p的值 ,p为素数

Input

第一行包含整数 n 。 接下来 n 行,每行包含一组 a , b , p

Output

共 n 行,每行输出一个询问的解。

Examples

Input

1
2 1  10007

Output

2

Hint

数据范围 1 ≤ n ≤ 20 ,    1 ≤ b ≤ a ≤ 1 × 1 0^18 ,    1 ≤ p ≤ 1 0^5