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
//siddhnata007

#include <bits/stdc++.h>
#include<algorithm>

const long long SZ = 1e5 + 7;
const long long inf = 1e18;
const long long mod = 1e9 + 7;
const long long MOD = 998244353;
 
#define si(x) 		scanf("%d",&x)
#define sl(x) 		scanf("%lld",&x)
#define ss(s) 		scanf("%s",&s)
#define pi(x) 		printf("%d\n",x)
#define pl(x) 		printf("%lld\n",x)
#define ps(s) 		printf("%s\n",s)
 
#define ll                  	long long
#define ld                 		long double
 
#define pb                  	push_back
#define mp                  	make_pair
 
#define pll                 	pair<ll, ll>
#define vi                  	vector<ll>
#define mi                  	map<ll, ll>
#define umi                 	unordered_map<ll, ll>
 
#define fi                  	first
#define se                  	second
#define Max(a,b)                ((a > b) ? a : b)
#define Min(a,b)                ((a < b) ? a : b)
 
#define all(c)              	(c).begin(), (c).end()
#define allr(c)             	(c).rbegin(), (c).rend()
 
#define dbg1(x)                 cout<<#x<<"="<<(x)<<endl;
#define dbg2(x,y)               cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<endl;
#define dbg3(x,y,z)             cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<" "<<#z<<"="<<(z)<<endl;
#define dbg4(x,y,z,w)           cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<" "<<#z<<"="<<(z)<<" "<<#w<<"="<<(w)<<endl;
 
#define ip1(X)               	ll X; cin>>X
#define ip2(X, Y)           	ll X, Y; cin>>X>>Y
#define ip3(X, Y, Z)       		ll X, Y, Z; cin>>X>>Y>>Z
#define ip4(W, X, Y, Z)   		ll W, X, Y, Z; cin>>W>>X>>Y>>Z
 
#define rep(i, n) 		        for (int i = 0; i < n; ++i)
#define repone(i, n) 		    for (int i = 1; i <= n; ++i)
#define reprange(i,a,b) 	    for(int i=(a);i<=(b);++i)
#define reprev(i,n) 		    for(int i=n;i>=0;i--)
 
using namespace std;
const char nline='\n';
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
     
}
// ll binpow(ll a, ll b) 
// {
//     ll res = 1;
//     while (b > 0) {
//         if (b & 1)
//             res = ((res%mod) * (a%mod))%mod;
//         a = ((a %mod)*( a%mod))%mod;
//         b >>= 1;
//     }
//     return res;
// }

// int sz = 1000007;
// vector<bool> primes(sz, true);
// void sieve_of_ert(void){
//     primes[0] = primes[1] = false;

//     for (int i = 2; i * i < sz; ++i){
//         if (primes[i]) {
//             for (int j = i * i; j < sz; j += i){
//                 primes[j] = false;
//             }
//         }
//     }
// }

// int swap (int a, int b){
//     a ^= b;
//     b ^= a;
//     a ^= b;

//     return a, b;
// }

 
int main()
{
	  ios::sync_with_stdio(false);
    cin.tie(NULL); // remove in interactive problem
    ip3(a, b, n);
    int req = 0;
    int ct = 0;
    while(n > req)
    {
        req = gcd(a, n);
        n -= req;
        ct++;

        req = gcd(b, n);
        n -= req;
        ct++;
    }

    if (ct & 2)
      cout<< 0;
    else
      cout<< 1;

	  return 0;
}
