← 返回题目列表

AtCoder · arc123_c

C. 1, 2, 3 - 分解

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

给定的是一个正整数 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).