Simon và Antisimon chơi một trò chơi. Ban đầu mỗi người nhận được một số nguyên dương cố định không thay đổi suốt trò chơi: Simon nhận số a và Antisimon nhận số b. Họ cũng có một đống n viên đá.

Hai người chơi thay phiên nhau, Simon đi trước. Ở lượt của mình, người chơi lấy khỏi đống đá đúng bằng ước chung lớn nhất giữa số cố định của anh ta và số viên đá hiện có (tức là lấy gcd(a, n) nếu là Simon, hoặc gcd(b, n) nếu là Antisimon). Nếu không thể lấy được số lượng đá yêu cầu (đống đá còn 0), người đó thua.

Nhiệm vụ: cho ba số a, b, n; hãy xác định ai là người chiến thắng.

Input: Ba số nguyên a, b, n (1 ≤ a, b, n ≤ 100).

Output: Nếu Simon thắng, in "0"; nếu Antisimon thắng, in "1".

Ví dụ

Input

3 5 9

Output

0

Input

1 1 100

Output

1