## MOD - Power Modulo Inverted

no tags

Given 3 positive integers x, y and z, you can find k = xy%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 = xy%z.

### Input

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

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
``` dhiren23: 2020-02-03 21:19:26 showing TLE even for T*sqrt(n) !! harsh_goyal152: 2020-01-11 10:45:28 what is input format ashish kumar: 2015-12-25 05:58:50 What should be expected time complexity. My T*sqrt(n)*logn is giving TLE. pardeep kumar: 2012-06-15 11:29:46 either x^y=z+k*n....for some positive integer n..OR z=x^y+k*n....for some positive integer n..correct me if i am wrong