Considerăm o împărţire de forma x1/x2/x3/.../xn, unde xi sunt numere naturale, pentru orice i (1≤i≤n). Împărţirea este evaluată efectuându-se calculele de la stânga la dreapta. De exemplu valoarea expresiei 1/2/1/2 este 1/4. Pentru a modifica ordinea de evaluare a expresiei se pot utiliza paranteze. De exemplu valoarea expresiei (1/2)/(1/2) este 1. Fiind dată o împărţire de acest tip este posibil, în unele cazuri, să fie utilizate câteva paranteze astfel încât la evaluare să se obţină o valoare întreagă.
Cerinţă
Scrieţi un program care citeşte din fişierul de intrare un set de expresii şi decide, pentru fiecare expresie în parte, dacă există sau nu posibilitatea de a fi utilizate la evaluarea ei câteva paranteze astfel încât valoarea rezultată să fie un număr întreg.
Date de intrare
Fişierul de intrare evaluare.in va conţine pe prima linie un număr natural d care reprezintă numărul de expresii care trebuie verificate. Pentru fiecare expresie, fişierul de intrare conţine o linie pe care este scrisă valoarea n care reprezintă numărul de întregi din expresie, apoi n linii care conţin în ordine numerele naturale x1, x2, ..., xn, câte un număr pe o linie.
Date de ieşire
Fişierul de ieşire evaluare.out va conţine exact d linii. Dacă expresia i (i ≤ d) poate fi transformată cu ajutorul parantezelor astfel încât la evaluare să se obţină un număr întreg, pe linia i se va scrie 1; în caz contrar linia i va conţine 0.
Restricţii
0 < d ≤ 5
2 ≤ n ≤ 10000
1 ≤ xi ≤ 1000000000
Exemple
evaluare.in
evaluare.out
Explicaţii
2
4
1
2
1
2
3
1
2
3
1
0
Fişierul de intrare conţine două expresii.
Prima expresie conţine 4 întregi: 1, 2, 1, 2 deci expresia este 1/2/1/2.
Prin inserarea parantezelor astfel (1/2)/(1/2) evaluarea va produce valoarea 1, care este un număr întreg, deci răspunsul este 1, care se scrie pe prima linie a fişierului de ieşire.
A doua expresie conţine 3 întregi: 1, 2, 3 deci expresia este 1/2/3.
Pentru această expresie nu există nici o posibilitate de a insera paranteze astfel încât evaluarea să producă o valoare întreagă, deci răspunsul este 0 care se va scrie pe linia a doua a fişierului de ieşire.
1
4
1
1
12
13
1
Fişierul de intrare conţine o expresie.
Aceasta conţine 4 întregi: 1, 1, 12, 13 deci expresia este 1/1/12/13.
Prin inserarea parantezelor astfel 1/((1/12)/13)) evaluarea va produce valoarea 156 care este număr întreg, deci răspunsul este 1, care se scrie pe prima linie a fişierului de ieşire.