\textit{Фізик-теоретик і математик займались однією і тією ж задачею, яка описувалась деяким рівнянням. Одного разу математик з радісним виглядом підбіг до фізика і сказав, що нарешті сьогодні він довів, що рівняння, яким вони займаються, має розв'язок.} \textit{- Дорогенький мій, - відповів йому фізик, поблажливо похлопавши його по плечу, - якби я хоч на хвилинку сумнівався, що розв'язок існує, то я б давно перестав займатись цією задачею!} \includegraphics{https://static.e-olymp.com/content/a1/a113905d33f3f67e0483ee563e72e24486123c9a.jpg} У Діми постійно відбувається внутрішня боротьба між Дімой-фізиком і Дімою-математиком. Його фізична частина стверджує, що наш світ ймовірнішу усього виник згідно законам теорії ймовірності і з великою долею ймовірності можна стверджувати, що подібне твердженння ймовірніше усього можна з великою долею ймовірності довести. У то й же час його математична частина вимагає чіткого математичного доведеня гіпотези ймовірнісного походження. Так як Діма зайнятий пошуками математичного доведення неймовірної проблеми у теорії ймовірності, він попросив Вас допомогти йому у розв'язанні більш простої задачі: "\textit{Чи має невід'ємний цілочисельний розв'язок при заданих цілочисельних коефіцієнтах рівняння }\textit{\textbf{ax + by = c}}\textit{?}". Так як для кожного рівняння йому не потрубен сам розв'язок, а роль відіграє знання самого факту існування розв'язку (саме цей факт Діма буде використовувати у ймовірнісному доведенні своєї неймовірної гіпотези), він просить Вас вивести \textbf{1} у випадку існування невід'много цілочисельного розв'язку і \textbf{0} у протилежному випадку. \InputFile Вхідні дані містять декілька тестових випадків, кількість яких наперед невідома. Кожне рівняння розміщеон у окремому рядку у вигляді \textit{\textbf{ax + by = c}} причому коефіцієнти при \textbf{x} і \textbf{y} рівні \textbf{1} пропускаються (\textbf{0} < \textbf{a}, \textbf{b} < \textbf{100000}; |\textbf{c}| < \textbf{1000000}). \OutputFile Для кожного тестового випадку у окремому рядку виведіть \textbf{1}, якщо вказаний розв'язок заданого рівняння існує, і \textbf{0} у протилежному випадку.