Forming Number

View as PDF

Submit solution

Points: 100
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C, C++, Java 11, JAVA 8, Python, ZIG

You are given a positive integer nn. You have infinite supplies of 11's, additions, multiplications and brackets for composing an expression. What is the least total number of additions and multiplications required to compose an expression evaluated into nn?

For example, n=9=(1+1+1)\times(1+1+1)n=9=(1+1+1)\times(1+1+1) can be evaluated with 55 operations and it is impossible to use 44 operations to compose an expression evaluated into 99. Therefore, you should output 55. Note that concatenating 11's is not allowed.

Input

First line contains the number of testcases TT. Each testcase is a line containing a positive integer nn.

Output

For each testcase, output a number indicating the minimum total number of additions and multiplications required.

Technical specifications

  • 1 \le T \le 10^41 \le T \le 10^4
  • 1 \le n \le 10^51 \le n \le 10^5

Sample Input 1

10
1
2
5
11
22
55
100
222
555
1000

Sample Output 1

0
1
4
7
9
11
13
15
18
20

Comments

There are no comments at the moment.