## 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

About 600 test cases.

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
```

hide comments
 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

 Added by: Fudan University Problem Setters Date: 2008-10-04 Time limit: 4s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: C99 ERL JS-RHINO NODEJS PERL6 VB.NET Resource: Folklore, description, standard program and test data by Blue Mary