Problem Statement

Given is a positive integer $N$. Consider a sequence of integers $A = (A_1, \ldots, A_K)$ that satisfies the conditions below:

• $\sum_{i=1}^K A_i = N$;
• each $A_i$ is a positive integer such that every digit in its decimal notation is $1$, $2$, or $3$.

Find the minimum possible value of $K$, that is, the number of elements in such a sequence $A$.

Process $T$ test cases per input file.

Constraints

• $1\leq T\leq 1000$
• $1\leq N\leq 10^{18}$

Input

Input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each case is in the following format:

N

Output

Print the answers.