给定 nnn 组询问，每组询问给定整数 a,b,pa,b,pa,b,p，计算 Cba(modp)C^a_b \pmod {p}Cba(modp) 的值。
保证 ppp 是质数。
输入
多组询问，第一行一个整数 n (1≤n≤20)n \ (1 \leq n \leq 20)n (1≤n≤20)。
接下来 nnn 行，每行两个整数 a,b,p (1≤b≤a≤1018,1≤p≤105)a,b,p \ (1 \leq b \leq a \leq 10^{18},1 \leq p \leq 10^5)a,b,p (1≤b≤a≤1018,1≤p≤105)。
输出
输出 nnn 行，每行输出一个询问的解。
样例
3 5 3 7 3 1 5 6 4 13
3 3 2