题目描述

给定一个正整数 $N$。考虑满足以下条件的整数序列 $A = (A_1, \ldots, A_K)$：

• $\\sum_{i=1}^K A_i = N$；
• 每个 $A_i$ 都是一个正整数，其十进制表示中的每个数字都是 $1$、$2$ 或 $3$。

找出满足上述条件的最小可能 $K$ 的值，也就是序列 $A$ 中元素的个数。

每个输入文件处理 $T$ 个测试用例。

约束条件

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

输入

从标准输入读入输入数据，输入格式如下：

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

每个测试用例的输入格式如下：

$N$

输出

输出结果。

示例输入1

5
456
10000
123
314
91

示例输出1

2
4
1
2
4

对于每个 $N$，一个最优的 $A$ 如下所示。

• 对于 $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)$。