Fișierul intrare/ieșire	cmmp1.in, cmmp1.out	Sursă	Info-Oltenia 2019 clasele 5-6
Autor	autor necunoscut	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.15 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Cmmp1 (clasele 7/8)

Notă: aceasta este problema cmmp cu limita de timp micșorată de la 1s la 0.15s. Este necesar să optimizați și implementarea, nu doar algoritmul.

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].

Cerință

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 cmmp1.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 cmmp1.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

• 1 ≤ N ≤ 10⁵
• 0 ≤ s[k] < 10⁵
• Pentru 20% din teste 0 ≤ s[k] < 10²
• Pentru 20% din teste 0 ≤ s[k] < 10³
• Dacă numărul dat este pătrat perfect, atunci operația „cmmp” îl lasă neschimbat
• Mărimea maximă a sursei: 10KB

Exemplu