Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Homework

By subeen · 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 nn, find the minimum number of digits which needs to be removed from nn so that nn becomes a perfect square without leading zeros. If there is no possible solution print 1-1.

Input

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

Following tt lines, contain an integer nn (1n1010)(1 \leq n \leq 10^{10}).

Output

Print tt lines with answer for each nn.

Sample

InputOutput
3
6434
625
333
2
0
-1

Discussion

Toph uses cookies. By continuing you agree to our Cookie Policy.