#198. 简单加密

迷糊间，4qwerty7 隐约想起 RSA 加密中对于私钥 $(d,\ n)$，用公钥加密后的报文 $m$ 的解密结果为 $m^d (mod\ n)$。

他就丢给你几个用公钥加密后的报文要你解密。

第一行一个整数 $T$ 表示有 $T(1\leq T \leq 10)$ 组数据。

之后 $T$ 行每行有空格分开的两个整数 $d,\ n,\ m(1\leq d,\ m\leq 2^{128},1\leq n \leq 2^{256})$ 分别表示一个私钥和一份用公钥加密后的报文。

对于每组测试数据输出一行一个整数，表示用私钥解密后的原始报文。

样例输入

1
4 19 5

样例输出

17