Problem Name : Integer Expressions

Problem Description:

The fourth standard Mathematics teacher wanted to create some Aha moments of discovery in his students. He puts slips of paper into a box, each slip containing one positive integer between 1 and 10000. He asks each student to pick a slip of paper from the box and try to build that number using only symbols from the set { “1” “+” “x” “(“ “)”} using the least number of symbols. In the symbols, “+” represents addition, “x” represents multiplication, and the normal precedence rules apply (a multiplication is done before addition unless brackets are used). The symbol “1” may be used one or more times to represent the numbers 1, 11, 111 or 1111. Of course the formulae must be valid arithmetical expressions, and unbalance brackets are not allowed.
For example, 24 = 11+11+1+1 and we have used only 9 symbols. A longer expression is 24 = (1+1) x (11+1), containing 12 symbols.
As you are much smarter than fourth standard students, we will give you more than one positive integers to express using these.

Constraints :
	3<N<15
	The integers to be represented will be less than 10000.
Input Format

	The first line will contain the number of expressions, N, that are needed to be discovered.
	The next N lines will have a positive integer each, which need to be represented in expressions of minimal length 	using the five symbols.

Output :
	The output will have N lines giving the length of the minimal expression for the corresponding number in the input.

Explanation :

Example 1

Input
3
24
12
33
Output
9
4
8

Explanation
There are three input numbers (N=3), and they are 24, 12 and 33. The representation for 24 takes 9 symbols “1+1+11+11” , 12 takes 4 symbols “11+1” and 33 takes 8 symbols “11+11+11”. The out is 9, 4 and 8 in three lines.

Example 2
Input
5
121
1331
122
222
333
Output
5
8
6
7
11

Explanation:

There are 5 inputs, 121, 1331, 122, 222, 333. The corresponding minimal expressions are “11x11”, “11x11x11”, “111+11”,”111+111”, “111x(1+1+1)”. With lengths 5,8,6,7,11 symbols respectively. Note that there may be multiple representations of the same number with the same length, even apart from the trivial case of changing the order of the symbols (111+11 or 11+111). For example 333=111x(1+1+1) =111+111+111, and both are the same length.