seuOJ198 - 简单加密

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：短码, 2019

题目描述

迷糊间，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