Discrete Logarithm

Time limit1sMemory limit128 MB

Summary

For each test case with prime P, base B, and target N, find the smallest L with B^L congruent to N mod P, or report no solution.

Level: Hard8 of 10
Topics: Math, Number theory, Hash map, Brute force
Solved: No attempts yet

Problem

Given a prime $P$ ( $2 \le P < 2^{31}$ ), an integer $B$ ( $2 \le B < P$ ), and an integer $N$ ( $1 \le N < P$ ), write a program that computes the discrete logarithm of $N$ with base $B$ modulo $P$ .

That is, find an integer $L$ satisfying the following condition:

$B^L \equiv N \pmod{P}$

Input

The input consists of several test cases. Each test case is a single line containing $P$ , $B$ , and $N$ separated by spaces. The input continues until the end of file.

Output

For each test case, print the discrete logarithm of $N$ on its own line. If more than one $L$ satisfies the condition, print the smallest such value. If no such $L$ exists, print no solution.

Hint

To solve this problem you need Fermat's little theorem, which is rarely used in ACM-ICPC contests. See Fermat's little theorem for details.

Examples1

Example 1

Input

5 2 1
5 2 2
5 2 3
5 2 4
5 3 1
5 3 2
5 3 3
5 3 4
5 4 1
5 4 2
5 4 3
5 4 4
12345701 2 1111111
1111111121 65537 1111111111

Expected output

0
1
3
2
0
3
1
2
0
no solution
no solution
1
9584351
462803587