Dãy số nguyên được xác định theo quy luật như sau:

~x_{0}~ = 1

~x_i~+1 = (a.~x_i~ + ~x_i~ div b) mod c

Đồng chí hãy tìm n nhỏ nhất sao cho tồn tại m < n và ~x_m~ = ~x_n~. Với n không quá 2.~10^7~

Giới hạn: 1 <= a <= ~10^4~ và 1 <= b, c <=~10^{14}~

Dữ liệu vào:

trong một dòng duy nhất chứa 3 số nguyên 1, b, c cách nhau bởi đấu cách.

Dữ liệu ra:

In ra giá trị n tìm được

Input

8 2 31

Output

9