Limits 1s, 512 MB

Matthew has purchased a new game and isn't feeling like completing his home work his teacher gave it to him. Can you help Matthew to complete his home work ?

The homework is :
Given an integer $n$, find the minimum number of digits which needs to be removed from $n$ so that $n$ becomes a perfect square without leading zeros. If there is no possible solution print $-1$.

Input

First line contains an integer $t$ $(1 \leq t \leq 50)$, the number of test cases.

Following $t$ lines, contain an integer $n$ $(1 \leq n \leq 10^{10})$.

Output

Print $t$ lines with answer for each $n$.

Sample

InputOutput
3
6434
625
333
2
0
-1

Submit

Login to submit.

Statistics

59% Solution Ratio
Lazy_ProgrammerEarliest, Nov '18
Tareq_AbrarFastest, 0.0s
LegendHabibLightest, 0 B
murad928Shortest, 343B
Toph uses cookies. By continuing you agree to our Cookie Policy.