在“计数诗歌朗诵”比赛中，表演者拿起麦克风，选择一个数字 $N$，并从 1 数到 $N$。也就是说，她先说 1，然后重复说出比上一个数字大 1 的数，直到说完 $N$ 为止。

现在轮到你表演了，但你觉得这个过程太乏味，想要增加一点花样来加快速度：有时，你不再是在上一个数字的基础上加 1，而是可以将该数字的各位数字反转（反转后产生的任何前导零将被移除）。例如，在说了“16”之后，你接下来可以说“17”或“61”；在说了“2300”之后，你接下来可以说“2301”或“32”。在一次表演中，你可以根据需要进行任意次数的反转（也可以不反转）。

你说的第一个数字必须是 1；为了达到数字 $N$，你需要说的最少数字个数是多少？1 和 $N$ 都计入总数。如果你多次说出同一个数字，每一次都单独计算。

输入格式

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

输出格式

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

数据范围

$1 \le T \le 100$。

小数据集（11 分）

$1 \le N \le 10^6$。

大数据集（14 分）

$1 \le N \le 10^{14}$。

样例

输入 1

3
1
19
23

输出 1

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

说明

在样例 2 中，翻转没有帮助，最优策略是直接数到 19。

在样例 3 中，最优策略是数到 12，翻转为 21，然后继续数到 23。也就是说，你说的数字序列为 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 21, 22, 23。