Description

在 Counting Poetry Slam 中，表演者拿起麦克风，选择一个数字 $N$，然后从 $1$ 开始大声数数直到 $N$。也就是说，她先说出 $1$，然后每次说出比上一个数字大 $1$ 的数字，直到说到 $N$ 为止。

现在轮到你表演了，但你觉得这个过程太无聊，想加点花样来加快进度：有时候，你可以选择不加 $1$，而是将当前数字的各位数字反转（去除反转后产生的前导零）。例如，在说完“16”后，你可以接着说“17”或者“61”；在说完“2300”后，你可以接着说“2301”或者“32”。你可以在表演过程中任意多次进行反转操作（也可以一次都不反转）。

你说的第一个数字必须是 $1$；请问，最少需要说多少个数字才能到达 $N$？$1$ 和 $N$ 都要计入总数。如果你多次说同一个数字，每次都要计数。

Input Format

第一行输入一个整数 $T$，表示测试用例的数量。接下来的 $T$ 行，每行一个整数 $N$，表示你需要到达的数字。

Output Format

对于每个测试用例，输出一行，格式为 "Case #$x$: $y$"，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是到达 $N$ 所需说出的最少数字个数。

3
1
19
23

Case #1: 1
Case #2: 19
Case #3: 15

Hint

样例解释

在第 2 个用例中，反转操作没有帮助，最优策略是直接数到 $19$。

在第 3 个用例中，最优策略是先数到 $12$，反转到 $21$，然后继续数到 $23$。你说出的数字依次为 $1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 21, 22, 23$。

数据范围

• $1 \leq T \leq 100$。

小数据范围

• 时间限制：5 秒。
• $1 \leq N \leq 10^6$。

大数据范围

• 时间限制：10 秒。
• $1 \leq N \leq 10^{14}$。

由 ChatGPT 4.1 翻译