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