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