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 dintre aceste casute este pozitionata inafara matricei, soarecele nu se poate deplasa in casuta respectiva.

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 nedreptatiti si vor depune plangere la sindicatul soarecilor de laborator.

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 ≤ 1000000$

* $1 ≤ N, M ≤ 10^9^$

* $1 ≤ P ≤ 2000000000$ (Nu vreti sa stiti de cata branza avem nevoie..)

* Pentru teste in valoare de $60$ de puncte: $1 ≤ N, M ≤ 400$.

* 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") ==