Cerința

Pentru orice număr natural x definim operația cmmp prin care adăugăm cifre la stânga lui x, la dreapta lui x sau la ambele capete ale lui x, astfel încât numărul obținut să fie pătrat perfect și cât mai mic posibil.
 
Se dau N numere naturale \( {s}_{1},{s}_{2}…{s}_{N} \).

Să se determine pentru fiecare număr s[k], 1 ≤ k ≤ N, cel mai mic pătrat perfect care se poate obține prin aplicarea operației cmmp.

Date de intrare

Fișierul de intrare cmmp.in conține pe primul rând numărul N. Pe linia a doua sunt scrise N numere naturale separate prin câte un spațiu.

Date de ieșire

În fișierul de ieșire cmmp.out vor fi scrise, în ordinea corespunzătoare citirii și separate prin câte un spațiu, cele N numere obținute din numerele date prin aplicarea operației cmmp.

Restricții și precizări

• 1 ≤ N ≤ 100.000
• 0 ≤ s[k] < 100.000
• Pentru 20% din teste 0 ≤ s[k] < 100
• Pentru 20% din teste 0 ≤ s[k] < 1000
• Dacă numărul dat este pătrat perfect, atunci operația cmmp îl lasă neschimbat.

Exemplu:

cmmp.in

4
21 0 19 80

cmmp.out

121 0 196 2809

Explicație

121 = 112, 0 = 02, 196 = 142, 2809 = 532