Let's define $F(x)$ as the sum of the digits of $x$. An integer $x$ is considered beautiful if $F(F(x)) = F(x)$.

You are given an integer $x$. In one move, you can choose any digit in the number and replace it with another. The resulting number cannot have leading zeros.

Your task is to calculate the minimum number of moves (possibly zero) required to make the given number beautiful.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The only line of each test case contains a single integer $x$ ($1 \le x \le 10^{18}$).

Output

For each test case, print a single integer — the minimum number of moves (possibly zero) required to make the given number beautiful.

Note

In the first example, the given number is already beautiful.

In the second example, in one move, we can get the beautiful number $3\underline{3}$ (the changed digit is underlined).

In the third example, in two moves, we can get the beautiful number $\underline{1}4\underline{0}$ (the changed digits are underlined).

Samples

4
1
37
645
2374236843276813

0
1
2
12