Splitting
A theoretical physicist and a mathematician were collaborating on a problem described by a particular equation. One day, the mathematician excitedly approached the physicist, announcing that he had finally proven the existence of a solution to their equation.
"My dear," the physicist replied, gently patting him on the shoulder, "if I had ever doubted that a solution existed, I would have stopped working on this problem long ago!"
Dima often finds himself torn between his physicist and mathematician personas. His physicist side argues that the universe likely emerged according to the laws of probability, and with high probability, this claim can be proven. Meanwhile, his mathematician side insists on a rigorous mathematical proof of this probabilistic origin hypothesis.
While Dima is preoccupied with finding a mathematical proof for a complex problem in probability theory, he has asked for your help with a simpler task: "Does the equation ax + by = c have a non-negative integer solution given integer coefficients?" Dima doesn't need the solution itself; he just needs to know whether a solution exists, as this fact will support his probabilistic proof of his remarkable hypothesis. Therefore, he requests that you output 1 if a non-negative integer solution exists, and 0 otherwise.
Input
The input consists of several test cases, with the number of cases unknown beforehand. Each equation is presented on a separate line in the format:
ax + by = c
Here, coefficients of x and y equal to 1 are omitted (0 < a, b < 100000; |c| < 1000000).
Output
For each test case, output 1 on a separate line if the given equation has a solution, and 0 otherwise.