After The Backstreet Boys' Reunion Tour plunged humanity into global lockdown and after consuming all Star Trek related content Gozz and Taylor decide to play a game to pass the time. Gozz and Taylor receive a number each a and b respectively. They also have a heap of n stones. The players take turns with Taylor (the second player) starting. During a move, a player should take from the heap the number of stones equal to the greatest common divisor of the fixed number they received and the number of stones left in the pile. A player wins when they cannot take the required number of stones (the heap has strictly less stones left than one needs).

Your task, as one of potentially several omniscient narrators, is to determine given \(a\), \(b\) and \(n\) who wins.

Input Specification

A single string containing three space-separated integers \(a\), \(b\) and \(n\) (\(1 \leq a,b,n \leq 100\)) - the fixed numbers Gozz and Taylor receive respectively and the initial size of the pile.

Output Specification

If Gozz wins print 0 and if Taylor wins, print 1.

Sample Input 1

3 6 9

Sample Output 1

0

Sample Input 2

1 2 100

Sample Output 2

0