题目描述

小Y发现，数学中有一个很有趣的式子：

$X^Y$ mod Z = K

给出X、Y、Z，我们都知道如何很快的计算K。但是如果给出X、Z、K，你是否知道如何快速的计算Y呢？

输入格式

本题由多组数据（不超过20组），每组测试数据包含一行三个整数X、Z、K。

输入文件一行由三个空格隔开的0结尾。

输出格式

对于每组数据：如果无解则输出一行No Solution，否则输出一行一个整数Y，使得其满足XY mod Z = K，如果有多个解输出最小的一个Y。

样例

5 58 33
2 4 3
0 0 0

9
No Solution

数据范围

• $0 \leqslant X, Z, K \leqslant 10^9$
• $0 \leqslant Y < Z$

来源

• BZOJ1467
• POJ3243
• 信息学奥赛之数学一本通
• stong9070整理