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-12-31 09:56:51
Very interesting problem!
2017-10-18 01:40:19
Looked like a walk in the park until the first WA. By the time I AC'd, my solution was an armour-plated bulldozer razing the park and half the town. An unexpected lesson in testing and debugging from this unassuming problem.

For those struggling, take it s-l-o-w and optimize later. AC in 0.80s beats 80 WAs. Testcase that helped me: 564 -> 7.
2017-04-27 00:54:18
@Arianto I cant seem to find any error with my code. can you provide me the test case that is failing in my case?
2017-04-04 16:40:03 manish kumar
@Arianto can you please check my submissions they are giving wrong answer and suggest any test case
2017-02-10 08:19:33
@ Arianto can you please check my submission and tell me why it is wrong?
2017-01-23 15:53:02
Why is there a WA, @Arianto please take a look.
2017-01-14 11:58:55
@ Arianto can you please check my submission and tell me why it is wrong?
2017-01-10 03:56:27 Arianto Wibowo
@Vipul: your algorithm doesnt always give the optimal solution :)

@kira28: thanks for pointing it out. exclamation mark removed :))

Last edit: 2017-01-10 03:59:28
2017-01-09 18:56:20 Vipul Srivastava
@ Arianto can you please check my submission and give some hint where I am going wrong?

Last edit: 2017-01-09 19:23:02
2017-01-09 12:31:09
@kira28: It is just X.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.