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

#### Technical specifications

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