\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}). \InputFile Для каждого тестового случая в отдельной строке выведите \textbf{1}, если указанное решение заданного уравнения существует, и \textbf{0} в противном случае.