== include(page="template/taskheader" task_id="far") ==

Fie o matrice de $N$ linii si $M$ coloane. Avem la dispozitie $P$ soareci, fiecare dintre acestia fiind dispusi sa parcurga matricea o data sau de mai multe ori dupa urmatoarele reguli:

Fie o matrice de $N$ linii si $M$ coloane. Avem la dispozitie $P$ soareci de laborator, fiecare dintre acestia fiind dispusi sa parcurga matricea o data sau de mai multe ori dupa urmatoarele reguli:

1) Un drum incepe in casuta $(1, 1)$ si se termina in causta $(N , M)$.
2) Daca la un moment dat soarecele se afla in casuta $(X , Y)$, atunci el se poate deplasa in casuta $(X + 1, Y)$, sau in casuta $(X, Y + 1)$. Evident, daca una din aceste casute este pozitionata inafara matricei, mutarea nu este valida.

1) Un drum incepe in casuta $(1, 1)$ si se termina in causta $(N, M)$.
2) Daca la un moment dat soarecele se afla in casuta $(X, Y)$, atunci el se poate deplasa in casuta $(X + 1, Y)$ sau in casuta $(X, Y + 1)$. Evident, daca una dintre aceste casute este pozitionata inafara matricei, soarecele nu se poate deplasa in casuta respectiva.

Dorim sa folosim soarecii pentru a parcurge fiecare drum posibil *exact* o data. Mai mult, dorim ca fiecare din cei $P$ soareci sa parcurga acelasi numar de drumuri. In caz contrar, unii soareci se vor simti

Dorim sa folosim soarecii pentru a parcurge fiecare drum posibil *exact* o data. Mai mult, dorim ca fiecare din cei $P$ soareci sa parcurga acelasi numar de drumuri. In caz contrar, unii soareci se vor simti nedreptatiti si vor depune plangere la sindicatul soarecilor de laborator.
 
Deoarece sindicatul ne-a mai cauzat probleme in trecut, vrem sa aflam daca o impartire echitabila a drumurilor este posibila pentru mai multe triplete $N M P$.

h2. Date de intrare

Fişierul de intrare $far.in$ ...

Fişierul de intrare $far.in$ contine pe prima sa linie un numar $T$.
Urmatoarele $T$ linii vor contine cate un triplet $N M P$, cu semnificatia din enunt.

h2. Date de ieşire

În fişierul de ieşire $far.out$ ...

Fişierul de ieşire $far.out$ va contine exact $T$ linii. Linia $i$ va contine numarul *1* daca exista o impartire echitabila pentru cazul $i$ sau numarul *0* in caz contrar.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N, M ≤ 10^9^$
* $1 ≤ P ≤ 2000000000$ (Nu vreti sa stiti de cata branza avem nevoie..)
* Pentru teste in valoare de $40$ de puncte: $1 ≤ N, M ≤ 400$.
* Pentru teste in valoare de $60$ de puncte: $1 ≤ N, M ≤ 10^6^$.
* *Atentie!* Observati ca numele problemei si numele fisierelor de intrare/iesire nu coincid.

h2. Exemplu
table(example). |_. far.in |_. far.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2
2 2 3
2 3 3
| 0
1

|
h3. Explicaţie

...

In primul caz exista 2 drumuri: $(1, 1)->(1, 2)->(2, 2)$, respectiv $(1, 1)->(2, 1)->(2 , 2)$. Avem mai multi soareci decat drumuri posibile, deci raspunsul este negativ.
In cel de-al doilea caz exista 3 drumuri: $(1, 1)->(2, 1)->(2 , 2)->(2, 3)$, $(1, 1)->(1, 2)->(2, 2)->(2 , 3)$, respectiv $(1, 1)->(1 , 2)->(1, 3)->(2 , 3)$. Avand 3 soareci, putem sa oferim fiecaruia cate un drum.

== include(page="template/taskfooter" task_id="far") ==