NPC2016C - Strange Waca

Waca loves maths,.. a lot. He always think that 1 is an unique number. After playing in hours, Waca suddenly realize that every integer can be represented by digit '1', plus operator and minus operator. For example, 1534 can be represented as 1111 + 1 + 111 + 111 - 11 - 11 + 111 + 111. In that case, there are total 7 operators (plus and minus).

Now, Waca wants to know, what is the minimum number of operators needed to achieve X

Input

First row is an integer T, the number of test cases.
Next T rows will each contain an integer, X, the number given to Waca

Output

For each test cases, print an integer, the minimum number of operators needed to achieve X.

Example

Input:
2
1534
219 Output: 7
4

Constraints:

  • 1 ≤ T ≤ 10
  • 1 ≤ X ≤ 1012

Added by:Louis Arianto
Date:2017-01-08
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:NPC Schematics 2016

hide comments
2017-01-09 11:57:21
The 4th line of the problem says:-
"Now, Waca wants to know, what is the minimum number of operators needed to achieve X!"
is that factorial(X) or just X ???
oh yes it was just X
AC!!!

Last edit: 2017-01-09 12:53:50
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.