AT_arc123_c [ARC123C] 1, 2, 3 - Decomposition

[problemUrl]: https://atcoder.jp/contests/arc123/tasks/arc123_c 正の整数 $ 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 $

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

### 制約 - $ 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) $