Bir nəzəriyyəçi fizik və bir riyaziyyatçı müəyyən bir tənliklə təsvir olunan bir problem üzərində əməkdaşlıq edirdilər. Bir gün, riyaziyyatçı həyəcanla fizikin yanına gəlib bildirdi ki, nəhayət, onların tənliyinin həllinin mövcudluğunu sübut edib.
"Əzizim," — fizik cavab verdi, onun çiyninə yüngülcə toxunaraq, — "əgər bir vaxtlar həllin mövcudluğuna şübhə etsəydim, bu problem üzərində çoxdan işləməyi dayandırardım!"
Dima tez-tez özündə fiziki və riyaziyyatçını bir arada hiss edir. Onun fizik tərəfi iddia edir ki, kainat ehtimallar qanunlarına əsasən yaranıb və böyük ehtimalla bu iddianı sübut etmək olar. Eyni zamanda, onun riyaziyyatçı tərəfi bu ehtimal mənşəli hipotezin ciddi riyazi sübutunu tələb edir.
Dima ehtimal nəzəriyyəsində çətin bir problemin riyazi sübutunu tapmaqla məşğul olduğu bir vaxtda, sizdən daha sadə bir məsələdə kömək istəyir: "Bütün əmsalları tam ədədi olan ax + by = c tənliyinin qeyri-mənfi tam ədədlərlə həlli varmı?" Dimaya həllin özünü tapmaq lazım deyil; ona sadəcə həllin mövcud olub-olmadığını bilmək kifayətdir — bu fakt onun möhtəşəm hipotezinin ehtimal sübutunu tamamlamağa kömək edəcək. Buna görə də, əgər qeyri-mənfi tam ədəd həlli mövcuddursa, **1**, əks halda isə **0** çap etməyinizi xahiş edir.
Girişdə neçə testin olduğu əvvəlcədən məlum deyil və bir neçə test verilir. Hər tənlik ayrıca sətrdə verilir və belə formatdadır:
ax + by = c
Burada və dəyişənlərinin əmsalı olduqda əmsal göstərilmir (0 < a, b < 100000; |c| < 1000000).
Hər bir test üçün, əgər verilmiş tənliyin qeyri-mənfi tam ədəd həlli varsa ayrıca sətrdə **1**, yoxdursa **0** çap edin.
Nümunə 1