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})$.