Раздвоение
Фізик-теоретик і математик займались однією і тією ж задачею, яка описувалась деяким рівнянням. Одного разу математик з радісним виглядом підбіг до фізика і сказав, що нарешті сьогодні він довів, що рівняння, яким вони займаються, має розв'язок.
- Дорогенький мій, - відповів йому фізик, поблажливо похлопавши його по плечу, - якби я хоч на хвилинку сумнівався, що розв'язок існує, то я б давно перестав займатись цією задачею!
У Діми постійно відбувається внутрішня боротьба між Дімой-фізиком і Дімою-математиком. Його фізична частина стверджує, що наш світ ймовірнішу усього виник згідно законам теорії ймовірності і з великою долею ймовірності можна стверджувати, що подібне твердженння ймовірніше усього можна з великою долею ймовірності довести. У то й же час його математична частина вимагає чіткого математичного доведеня гіпотези ймовірнісного походження.
Так як Діма зайнятий пошуками математичного доведення неймовірної проблеми у теорії ймовірності, він попросив Вас допомогти йому у розв'язанні більш простої задачі: "Чи має невід'ємний цілочисельний розв'язок при заданих цілочисельних коефіцієнтах рівняння ax + by = c?". Так як для кожного рівняння йому не потрубен сам розв'язок, а роль відіграє знання самого факту існування розв'язку (саме цей факт Діма буде використовувати у ймовірнісному доведенні своєї неймовірної гіпотези), він просить Вас вивести 1 у випадку існування невід'много цілочисельного розв'язку і 0 у протилежному випадку.
Вхідні дані
Вхідні дані містять декілька тестових випадків, кількість яких наперед невідома. Кожне рівняння розміщеон у окремому рядку у вигляді
ax + by = c
причому коефіцієнти при x і y рівні 1 пропускаються (0 < a, b < 100000; |c| < 1000000).
Вихідні дані
Для кожного тестового випадку у окремому рядку виведіть 1, якщо вказаний розв'язок заданого рівняння існує, і 0 у протилежному випадку.