C - 1, 2, 3 - Decomposition Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

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

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

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

一つの入力ファイルにつき、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)

Score : 600 points

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.

Sample Input 1

5
456
10000
123
314
91

Sample Output 1

2
4
1
2
4

For each N, one optimal A is shown below.

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