The cost of a positive integer $n$ is defined as the result of dividing the number $n$ by the sum of its digits.

For example, the cost of the number $104$ is $\frac{104}{1 + 0 + 4} = 20.8$, and the cost of the number $111$ is $\frac{111}{1 + 1 + 1} = 37$.

You are given a positive integer $n$ that does not contain leading zeros. You can remove any number of digits from the number $n$ (including none) so that the remaining number contains at least one digit and is strictly greater than zero. The remaining digits cannot be rearranged. As a result, you may end up with a number that has leading zeros.

For example, you are given the number $103554$. If you decide to remove the digits $1$, $4$, and one digit $5$, you will end up with the number $035$, whose cost is $\frac{035}{0 + 3 + 5} = 4.375$.

What is the minimum number of digits you need to remove from the number so that its cost becomes the minimum possible?

Input

The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The only line of each test case contains a positive integer $n$ ($1 \leq n \lt 10^{100}$) without leading zeros.

Output

For each test case, output one integer on a new line — the number of digits that need to be removed from the number so that its cost becomes minimal.

Samples

4
666
13700
102030
7

2
4
3
0