Description

众所周知RSA的公私钥的制作过程是：

1. 选取两个不同的质数$p_1, p_2$；

2. 计算$n=p_1 \times p_2$；

3. 选公钥：与$\varphi(n)$互质的整数$E$，且$1<E< \varphi (n)$；

4. 算私钥：满足$(D*E) \% \varphi(n) = 1$的整数$D$；

期间所有出现的数字均为正整数，$\varphi(n)$为对$n$求欧拉函数。

现在你是生成私钥的一方，你只有$p_1$和$p_2$和$E$，求$D$。

Input Format

对于每个测试用例，三个整数，分别代表 $p1,p2,E$。

题目的数据范围：$2 \le p_1, p_2, E \le 30000$。

Output Format

对于每个测试用例，输出一个整数表示结果。

题目答案不唯一，给出任一答案都视为正确。

3 11 3

7

Source

Online Judge http://127.0.0.1