题目描述

正の整数 $N$ が与えられます。整数列 $A\ =\ (A_1,\ \ldots,\ A_K)$ であって以下の条件を満たすものを考えます：

• $\sum_{i=1}^K\ A_i\ =\ N$
• 各 $A_i$ は正の整数で、$10$ 進法表記したときどの桁の値も $1,\ 2,\ 3$ のいずれかである。

そのような $A$ の要素数 $K$ として考えられる最小の値を答えてください。

一つの入力ファイルにつき、$T$ 個のテストケースに答えてください。

输入格式

入力は以下の形式で標準入力から与えられます。

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

各テストケースは以下の形式で与えられます。

$N$

输出格式

答えを出力してください。

题目大意

题目描述

给出一个正整数 $n$ ，求 $n$ 至少可以表示为多少个 「十进制下仅含有 $1,2,3$ 的正整数」 的和？

翻译 by _FJqwq

输入格式

单测试点包含多组数据，共 $T+1$ 行。

第 $1$ 行，包括一个正整数 $T$，表示 $T$ 组询问。

接下来 $T$ 行，每行包括一个正整数 $n$，表示询问。

输出格式

共 $T$ 行，每行一个正整数，表示对应询问的答案。

样例解释

样例#1

456 = 133 + 323
10000 = 323 + 3132 + 3232 + 3313
123 = 123
314 = 312 + 2
91 = 22 + 23 + 23 + 23

5
456
10000
123
314
91

2
4
1
2
4

提示

制約

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

Sample Explanation 1

それぞれの $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)$