SufixeShnasty

Cerință

Un număr este "shnasty" dacă este nenul și are număr impar de divizori.
De exemplu $1$ și $9$ sunt numere shnasty dar $6$ sau $11$ nu sunt.

Un sufix al unui număr este orice parte obținută păstrând ultimele câteva cifre ale lui.
De exemplu sufixele numărului $4341$ sunt: $4341$, $341$, $41$ și $1$.

Se dă $N$ precum și $N$ numere, pentru fiecare număr trebuie să spunem câte dintre sufixele lui sunt shnasty.

Date de intrare

Pe prima linie se găsește $N$. Pe următoarele $N$ rânduri se va afla câte un număr pentru care trebuie să rezolvăm problema.

Date de ieșire

Se vor afișa $N$ rânduri, numărul de prefixe shansty ale fiecărui număr.

Restricții și precizări

• $1 \leq N \leq 2*10^5$;
• $1 \leq$ Numerele citite $\leq 10^{12}$;
• Dacă cumva sufixul numărului începe cu $0$ dar este nenul, va fi considerat valid. De exemplu: pentru că $16$ este shnasty numărul $1016$ are două sufixe shnasty: $016$ și $16$, ambele numere în bază $10$ reprezintă valoarea $16$.

Subtaskuri

• Pentru $10p : N = 1$ și numărul citit are maxim $6$ cifre.
• Pentru alte $20p :$ Numerele citite au maxim $4$ cifre
• Pentru alte $40p :$ Numerele citite au maxim $6$ cifre

Exemplul 1

stdin

7
100
316
464
332
281
121
225

stdout

1
1
2
0
2
2
2

Explicație

De exemplu:
$100$ are sufixele: $100$, $0$ și $0$. Singurul shnasty este $100$ (trebuie să fie nenule).
$316$ are ca sufix shnasty, sufixul $16$.
$332$ nu are niciun sufix shnasty.
$121$ are sufixele shnasty $121$ și $1$.
$225$ are sufixele shnasty $225$ și $25$.

Exemplul 2

stdin

1
81225

stdout

4