Dado un número entero positivo ~N~. Considere una secuencia de números enteros ~A = (A_1, ..., A_K)~ que cumpla:

$$\displaystyle \sum_{i=1}^{k} {A_i} = N$$

y que cada ~A_i~ sea un número entero positivo tal que cada dígito en su notación decimal es ~1~, ~2~ ó ~3~

Encuentre el valor mínimo posible de ~K~, es decir, el número de elementos en dicha secuencia ~A~.

Entrada

Procese ~T~ casos de prueba por archivo de entrada.

T
N_1
N_2
.
.
.
N_T

Salida

answer1
answer2
.
.
.
answerT

Subtareas

• Subtarea 1 (30 puntos): ~T \leq 1000, N \leq 10000~.
• Subtarea 2 (70 puntos): ~T \leq 1000, N \leq 10^{18}~.

Ejemplo de Entrada

5
456
10000
123
314
91

Ejemplo de Salida

2
4
1
2
4

Para cada ~N~, una secuencia ~A~ óptima se muestra a continuación:

• ~N = 456, A = (133, 323)~
• ~N = 10000, A = (323,3132,3232,3313)~
• ~N = 123, A = (123)~
• ~N = 314, A = (312,2)~
• ~N = 91, A = (22,23,23,23)~