Description

有一个数列a ，a_0=1, a_i+1 = (A*a_i+a_i mod B)mod C要求这个数列第一次出现重复的项的标号。

Format

Input

一行三个数，分别表示A,B,C 。

Output

输出第一次出现重复项的位置，如果答案超过2*10^6输出-1 。

Samples

2 2 9

4

Data Size & Hint

30%的数据 A,B,c<=10^5；

100%的数据A,B,C<=10^9 。