Given 3 positive integers x, y and z, you can find k = x^y%z easily, by fast power-modulo algorithm. Now your task is the inverse of this algorithm. Given 3 positive integers x, z and k, find the smallest non-negative integer y, such that k%z = x^y%z.

Input

About 600 test cases.

Each test case contains one line with 3 integers x, z and k.(1<= x, z, k <=10⁹)

Input terminates by three zeroes.

Output

For each test case, output one line with the answer, or "No Solution"(without quotes) if such an integer doesn't exist.

Example

Input:
5 58 33
2 4 3
0 0 0

Output:
9
No Solution