Spoj3105 Mod

已知数 $a, p, b$，求满足 $a^x\equiv b\pmod p$ 的最小自然数 $x$。

输入格式

每个测试文件中最多包含 $100$ 组测试数据。

每组数据一行，包含 $3$ 个正整数 $a, p, b$。

当 $a=p=b=0$ 时，表示测试数据读入完毕。

输出格式

对于每组数据，输出一行。

如果无解，输出 No Solution（不含引号），否则输出最小自然数解。

样例输入

5 58 33
2 4 3
0 0 0

样例输出

9
No Solution

样例解释

第一组数据中 $5^9=1953125=58\times 33674+33$，故 $5^9\equiv 33\pmod{58}$，且 $9$ 是最小的自然数解。

第二组数据中 $2^x\bmod 4$ 只可能取 $1$（$x=0$）、$2$（$x=1$）或 $0$（$x\ge 2$），永远取不到 $3$，因此无解。

数据范围

• 对于 $100\%$ 的数据，$a, p, b\le 10^9$；
• 每个测试文件最多 $100$ 组数据。

来源与许可

本题为 SPOJ 3105 试题「Mod」，题面与测试数据整理自 BZOJ 2480。

样例 1

输入

5 58 33
    2 4 3
    0 0 0

输出

9
No Solution