## Forming Number

View as PDF

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 . You have infinite supplies of '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 ?

For example, can be evaluated with operations and it is impossible to use operations to compose an expression evaluated into . Therefore, you should output . Note that concatenating 's is not allowed.

#### Input

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

#### Output

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

#### 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