Fragrant numbers

Problem Description

Many people love numbers, and some have a penchant for specific numbers. Nowadays in popular culture, 1145141919 is a very fragrant number, and many people want to represent all other numbers with this number. Let $S$ be an infinite string of "1145141919" infinitely stitched together as "114514191911451419191145141919...". Take a prefix $T$ of $S$ , you can insert '$($' , '$)$' , '$+$' or '$*$' to $T$ to form a new string $T'$, and then let the value of $T'$ be $val(T')$ according to ordinary rules. (You can insert any number of operators, even 0. But need to ensure that the inserted operators form legitimate operations) Now for a number $N$, please calculate the minimum length of $T$ that can make $val(T')=N$. For example, when $N=520$, the minimum length of $6$ (pick the first $6$ characters $114514$ and insert operators to make $T'=1+1+4+514$ , then we have $val(T')=520$ ) If no such $T$ exists, output $-1$.

Input

There are multiple test cases. The first line with a number $t$ indicates the number of test cases. For each test case, one integer $N$ per line indicates an inquiry. $1≤t≤30$ $1≤N≤5000$

Output

Output $t$ lines. One integer per line indicates the corresponding answer.

Sample Input

3
520
1
2

Sample Output

6
1
2

Source

2020 Multi-University Training Contest 6