Uolevi recently realized he wants to be a logger. He was asked by Roope from Red Hammer Logging to seize some logs from a nearby forest.

Roope asked Uolevi to log discreetly. Unfortunately Uolevi misheard, so now he is troubled, since he heard that the discrete log problem is very hard. Therefore he wants you to help him solve it.

Input

The only line of input contains three integers a b p. It is guaranteed that p is prime.

Output

Output the least non-negative integer k (0 is non-negative), such that a^{k} = b \text{ }(\text{ mod } p\text{ }). If no such integer exists, output -1.

Constraints

• 1 \leq a, b < p \leq 10^{12}
• p is prime

Example

Input:

2 3 5

Output:

3

Input:

4 3 5

Output:

-1