你需要构建一对正整数。为此，给定一个包含十进制数字的列表。你必须恰好使用列表中的每一个数字一次，但你可以选择哪些数字用于第一个整数，哪些数字用于第二个整数。你还可以选择每个整数内数字的顺序，但不能将零放在任何一个整数的最高位（最左侧）。注意，你也不能只选择一个零作为其中一个整数，因为它必须是正整数。

例如，给定列表 $[1, 0, 2, 0, 4, 3]$。你可以构建的有效整数对包括 $(200, 143)$ 和 $(3, 12400)$。另一方面，以下整数对是无效的：

• $(0102, 34)$：有前导零。
• $(0, 12340)$：包含非正整数。
• $(10, 243)$ 和 $(12300, 47)$：每一对中使用的数字列表与给定的数字列表不完全匹配。

给定要使用的数字列表，可以实现的两个构建出的整数之间的最小绝对差是多少？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 行。每一行描述一个测试用例，包含一个数字字符串 $D$。$D$ 中的每个字符都是你必须使用的数字。

输出格式

对于每个测试用例，输出一行包含 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是根据上述规则由 $D$ 构建出的两个整数之间可能达到的最小绝对差。

数据范围

$1 \le T \le 100$。 $D$ 中的每个字符都是十进制数字。 $D$ 中至少有两个字符不是 $0$。

子任务 1

$2 \le$ $D$ 的长度 $\le 8$。

子任务 2

$2 \le$ $D$ 的长度 $\le 36$。

样例

样例输入 1

4
1234
0011
07080
0899

样例输出 1

Case #1: 7
Case #2: 0
Case #3: 620
Case #4: 1

说明

对于样例 1，构建出的最优整数对是 $31$ 和 $24$；对于样例 2，是 $10$ 和 $10$；对于样例 3，是 $700$ 和 $80$；对于样例 4，是 $89$ 和 $90$。