АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Саймон Анти-саймонтой дараах тоглоомоор тоглож байлаа. Саймонд a тоо Анти-саймонд b
тоо байгаа ба энэ тоо нь тоглоомын турш өөрчлөгдөхгүй.

Тэдэнд бас n чулуутай хайрцаг өгөгджээ. Саймоноос эхлэн тоглогчид ээлжиндээ тоглогч хайрцагнаас өөрийнх нь тогтмол ба хайрцганд байгаа чулууны тоо хоёрын хамгийн их ерөнхий хуваагчтай тэнцүү тоог авна. Ийнхүү ээлжилж тоглосоор үйлдлээ хийж чадахгүй болсон тоглогч хожигдоно. (Өөрөөр хэлбэл үйлдэл хийх үед нь хайрцганд чулуу байхгүй байвал).

Энэ тоглоомонд хэн нь хожихыг тодорхойл.

Input

Зайгаар тусгаарлагдсан a, b, n (1 ≤ a, b, n ≤ 100) тоонууд өгөгдөнө.

Output

Саймон хожвол "0", үгүй бол "1" гэж хэвлэнэ.

Example

Input 1:

3 5 9

Output 1:

0

Input 2:

1 1 100

Output 2:

1