reducere

LLM definește operația de $reducere$ a unui număr $X$ astfel:

Fie $X$ = $\overline{x_1 x_2 x_3 ... x_k}$.
Putem alege poziția unei cifre, fie aceasta $t$ cu condiția că $1 < t \leq k$ și a o elimina.
Astfel $X$ devine $\overline{x_1 x_2 ... x_{t-1} x_{t+1} x_{t+2} ... x_k}$

Se dau numerele $P$, $N$ și șirul $a_1, a_2, ..., a_N$. LLM are două tipuri de întrebări pentru tine și te roagă să îi dai răspunsul corect la ambele tipuri de întrebări.

Cerință

Dacă $P = 1$, LLM te roagă să afișezi un șir de $N$ numere, al $i$-lea număr fiind $1$ dacă $a_i$ este pătrat perfect, $0$ altfel.

Dacă $P = 2$, LLM te roagă să afișezi un șir de $N$ numere naturale, al $i$-lea număr reprezentând numărul de moduri diferite în care se poate reduce numărul $a_i$ la un pătrat perfect.

Date de intrare

Pe prima linie a fișierului de intrare reducere.in se află două numere naturale $P$ și $N$ separate printr-un spațiu. Pe următoarea linie se află $N$ numere naturale separate prin câte un spațiu reprezentând șirul $a_i$.

Date de ieșire

Dacă $P = 1$, pe prima linie din fișierul de ieșire reducere.out se află șirul de $N$ numere naturale separate prin câte un spațiu. Dacă $P = 2$, pe prima linie din fișierul de ieșire reducere.out se află șirul de $N$ numere naturale separate prin câte un spațiu.

Restricții și precizări

• $P = 1$ sau $P = 2$.
• $1 \leq N \leq 100 \ 000$
• $1 \leq a_i \leq 10^9$ oricare ar fi $1 \leq i \leq N$.
• Două operații de $reducere$ se consideră diferite dacă poziția cifrei reduse este diferită.
• Pentru 40 de puncte $P = 1$.
• Pentru 20 de puncte $P = 2$ și $a_i < 100$.

Exemplul 1

reducere.in

1 5
64 10 100 36 63

reducere.out

1 0 1 1 0

Exemplul 2

reducere.in

2 5
102 81000 99 369 2256

reducere.out

0 3 1 1 2

Explicații

În primul exemplu, $64 = 8^2$, $100 = 10^2$, $36 = 6^2$.

În al doilea exemplu:

Numerele obținute prin reducere a numărului $102$ sunt $10$ și $12$, care nu sunt pătrate perfecte.

Pătratele perfecte obținute prin reducerea numărului $81000$ sunt $8100$, $8100$ și $8100$.

Pătratul perfect obținut prin reducerea numărului $99$ este $9$.

Numerele obținute prin reducere a numărului $369$ sunt $36$ și $39$, $36$ fiind pătrat perfect.

Numerele obținute prin reducere a numărului $2256$ sunt $256$ și $226$, și $225$, doar $226$ nu este pătrat perfect.