Powtop

Definim o putere ca fiind un număr natural $P$ cu proprietatea că există alte două numere naturale $A > 1$ și $B > 1$ astfel încât $P = A ^ B$. Exemple de puteri: $8 = 2^3$; $625 = 5^4$; $7 \ 776 = 6^5$.

Asupra unui un șir de $N$ numere naturale $S_i$, $1 \leq i \leq N$, se aplică următorul algoritm:

• Termenii șirului $S_i$, $1 \leq i \leq N$, se transformă într-un alt șir cu $N-1$ înmulțind fiecare doi termeni consecutivi.
• Se reia operația anterioară până când se obține un șir format dintr-un singur termen.

De exemplu: $S = [1,2,3,4] \rightarrow [2,6,12] \rightarrow [12,72] \rightarrow [864]$

Cerință

Se consideră $\boldsymbol{T}$ șiruri notate cu $X_i$, $1 \leq i \leq T$, de câte $N$ numere naturale fiecare. Pentru fiecare dintre cele $T$ șiruri $X_i$, $1 \leq i \leq T$, se aplică algoritmul descris mai sus atât pentru șirul dat cât și pentru cele $N - 1$ permutări circulare către stânga ale șirului $X_i$, $1 \leq i \leq T$.

Să se determine pentru fiecare șir $X_i$, $1 \leq i \leq T$, care dintre termenii obținuți sunt puteri.

Date de intrare

Fișierul de intrare powtop.in conține pe primul rând numerele naturale $T$ și $N$, iar pe următoarele $T$ linii câte $N$ numere naturale ale șirului $X_i$, $1 \leq i \leq T$.

Date de ieșire

Fișierul de ieșire powtop.out trebuie să conțină $T$ linii cu câte $N$ numere de $0$ sau $1$ fiecare:
$0$ dacă termenul obținut prin aplicarea algoritmului nu este putere sau $1$ dacă este putere. Numerele aflate pe aceeași linie trebuie separate prin câte un spațiu.

Restricții și precizări

• $1 \leq T \leq 100$
• $2 \leq N \leq 50$
• $1 \leq X_i \leq 10^7, 1 \leq i \leq N$

Exemplul 1

powtop.in

2 4
2 6 3 12
3 8 16 9

powtop.out

0 0 1 0
1 0 0 0

Explicație

$T = 2$, $N = 4$ și avem două șiruri: $X_1$ = $[2,6,3,12]$ și $X_2$ = $[3,8,16,9]$.

Prin aplicarea algoritmului pentru primul șir se obține numărul $139 \ 968$, care nu este putere. Pentru următoarele $3$ permutări circulare la stânga se obțin numerele $559 \ 872$, $248 \ 832$ și $62 \ 208$. Dintre acestea, doar $248 \ 832$ = $12^5$ este putere.

Prin aplicarea algoritmului pentru al doilea șir se obține numărul $56 \ 623 \ 104 = 384^3$, care este putere. Pentru următoarele $3$ permutări circulare la stânga se obțin numerele $71 \ 663 \ 616$, $2 \ 519 \ 424$ și $1 \ 990 \ 656$, care nu sunt puteri.