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