Description

Given $a,p,b$, find the smallest non-negative integer $x$ such that $a^x≡b \pmod p$.

Input Format

Each test file contains several test cases, with the guarantee that $\sum \sqrt p\le 5\times 10^6$.

Each test case consists of one line with $3$ positive integers $a,p,b$.

When $a=p=b=0$, it indicates the end of input.

Output Format

For each test case, output one line.

If there is no solution, output No Solution. Otherwise, output the smallest non-negative integer solution.

5 58 33
2 4 3
0 0 0

9
No Solution

Hint

For $100\%$ of the testdata, $1\le a,p,b\le 10^9$ or $a=p=b=0$.

2021/5/14 strengthened by SSerxhs.
2021/7/1 added a set of hack testdata.

Translated by ChatGPT 5