Background

Special for beginners, ^_^

Description

有一个数列 $a_n$，$a_0=1,a_{i+1}=(A×a_i+a_i \bmod B) \bmod C$，要求这个数列第一次出现重复的项的标号。

Format

Input

一行三个数，分别表示 A,B,C（都<=1.2e9）。

Output

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

Samples

2 2 9

4

Limitation

1s, 1024KiB for each test case.