seuOJ385 - 拆数

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：短码, 决赛, 2022

题目描述

给定正整数 $x$ ，你需要将它拆成若干个正整数的和，使得这些正整数的数位上只有 $1,2,3$。

要求最小化拆成的数的个数。

输入格式

第一行一个数 $T\ (T\leq 30000)$ 表示数据组数。

然后 $T$ 行，每行一个正整数 $x\ (x\leq 10^{18})$ 表示需要拆分的数。

输出格式

每组数据输出一个数表示最少要拆分的数量。

样例

样例输入

5
7
10
398
718921
182347342642348324

样例输出

3
4
3
4
5