All submissions for this problem are available.The chef is a top coder and he had a girlfriend who is weak at coding. Once she was given a task to solve a Coding number. Now you need to help the chef to solve his girlfriend's problem Let's call a positive integer $N$ a Coding number if the following conditions are satisfied: The decimal value of $N$ will not contain any Zeros. If we add the squares of decimal digits is $X$, then $X$ is a perfect square Now the problem is you need to find the number of 1's in the smallest coding number of $N$ digits. ### Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of T test cases follows. - The first and only line of each test case contains a single integer$N$. ### Output - For each test case, print the count of 1's in the decimal representation of the smallest coding number or -1 if it doesn't have any coding number. ### Constraints - $1 \leq T \leq 100$ - $1 \leq N \leq 105$ - The sum of $N$ over all test cases does not exceed 105 ### Example Input 2 1 3 ### Example Output 1 1 ### Explanation Example case 1: It is obvious that 1 is the coding number. Example case 2: Since 122 is the coding number it contains only one $1's$
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.