Simon and Antisimon play a game. Initially each player receives one fixed positive integer that doesn't change throughout the game. Simon receives number *a* and Antisimon receives number *b*. They also have a heap of *n* stones. The players take turns to make a move and Simon starts. During a move a player should take from the heap the number of stones equal to the greatest common divisor of the fixed number he has received and the number of stones left in the heap. A player loses when he cannot take the required number of stones (i. e. the heap has strictly less stones left than one needs to take). 

Your task is to determine by the given *a*, *b* and *n* who wins the game.
The only string contains space-separated integers *a*, *b* and *n* (1 ≤ *a*, *b*, *n* ≤ 100) — the fixed numbers Simon and Antisimon have received correspondingly and the initial number of stones in the pile.
3 5 9
0
1 1 100
1
23 12 16
1
95 26 29
1
73 32 99
1
1 1 1
0
41 12 65
1
13 61 100
1
100 100 10
0
12 24 26
1
73 21 96
1
17 22 81
1
14 88 97
1
42 81 17
0
34 36 19
1
21 87 12
1
97 92 98
1
49 25 62
1
29 17 44
1
10 1 10
0
99 98 100
1
100 100 1
0
11 99 55
0
8 13 21
0
34 55 89
0
21 34 55
1
13 21 34
1
34 21 55
0
10 20 84
1
4 2 5
0
3 2 3
0
31 23 1
0
100 100 100
0
100 1 100
0
1 100 100
1
1 1 100
1
17 23 100
1
99 98 100
1
1 1 2
1
2 1 1
0
1 2 1
0
2 1 2
0
10 10 3
1
2 2 1
0
9 5 1
0
# Семен и Антисемен играют в игру. Изначально каждому игроку дано одно
# фиксированное целое положительное число, которое не меняется в процессе
# игры. Семену дано число a, Антисемену дано число b. Также у них есть
# кучка из n камней. Игроки ходят по очереди, первый ход делает Семен.
# На своем ходу игрок должен взять из кучки число камней, равное наибольшему
# общему делителю данного ему числа и количества оставшихся камней в кучке.
# Проигрывает тот, кто не сможет взять требуемое число камней (по причине
# того, что в кучке остается строго меньше камней, чем нужно взять).
#
# Ваша задача — по заданным a, b и n определить, кто выиграет в этой игре.
#
# Входные данные
# В единственной строке через пробел записаны целые числа
# a, b и n (1 ≤ a, b, n ≤ 100) — числа, данные Семену и Антисемену
# соответственно, и исходное количество камней в кучке.
#
# Выходные данные
# Если выиграет Семен, выведите «0» (без кавычек),
# иначе выведите «1» (без кавычек).

# 3 5 9
# 0

# 1 1 100
# 1

# Примечание
# Наибольшим общим делителем двух неотрицательных целых чисел a и b
# называется такое наибольшее положительное целое число k,
# что a делится на k без остатка, и, аналогично, b делится на k
# без остатка. Обозначим через gcd(a, b) операцию вычисления
# наибольшего общего делителя чисел a и b.
# В частности, gcd(x, 0) = gcd(0, x) = x.
#
# В первом примере игра будет идти следующим образом:
#
# Семен должен взять из кучки gcd(3, 9) = 3 камня. После его хода в
# кучке остается 6 камней.
# Антисемен должен взять из кучки gcd(5, 6) = 1 камень. После его хода в
# кучке остается 5 камней.
# Семен должен взять из кучки gcd(3, 5) = 1 камень. После его хода в
# кучке остается 4 камня.
# Антисемен должен взять из кучки gcd(5, 4) = 1 камня. После его хода в
# кучке остается 3 камня.
# Семен должен взять из кучки gcd(3, 3) = 3 камня. После его хода в
# кучке остается 0 камней.
# Антисемен должен взять из кучки gcd(5, 0) = 5 камня.
# Так как 0 < 5, это сделать невозможно, и Антисемен проигрывает.
# Во втором примере каждый игрок на каждом ходу берет из кучки
# по одному камню. Так как n четное, последний камень возьмет
# Антисемен, а Семен после этого не сможет сделать ход.


def gcd(x, y):
    while y > 0:
        x, y = y, x % y
    return x

a, b, n = map(int, input().split())

while n >= 0:
    n = n - gcd(a, n)
    if n < b:
        t = 0
        break
    n = n - gcd(b, n)
    if n < a:
        t = 1
        break

print(t)
