Little Mono 是一个聪明的孩子，他能快速进行复杂的算术运算。但他只认识一个数字 $D$ ($1 \le D \le 9$)。他想用他唯一认识的这个数字来构造表达式以表示整数。

一个合法的表达式可以按如下方式生成：

1. 任何仅由数字 $D$ 组成的数都是合法表达式。例如，如果 $D = 1$，则 $1, 11, 111, \dots$ 都是合法表达式。
2. 如果 $A$ 和 $B$ 是合法表达式，则 $(A) + (B)$ 是合法表达式。
3. 如果 $A$ 和 $B$ 是合法表达式，则 $(A) - (B)$ 是合法表达式。
4. 如果 $A$ 和 $B$ 是合法表达式，则 $(A) * (B)$ 是合法表达式。
5. 如果 $A$ 和 $B$ 是合法表达式，则 $(A) / (B)$ 是合法表达式。（此处的 $/$ 产生精确值，而非整数除法，且表达式 $A$ 的结果必须为非零值）
6. 如果 $A$ 和 $B$ 是合法表达式，则 $(A)^{(B)}$ 是合法表达式。（表达式 $A$ 的结果必须为非负值）
7. 如果 $A$ 是合法表达式，则 $\sqrt{(A)}$ 是合法表达式。（表达式 $A$ 的结果必须为非负值）重要提示：一个合法表达式最多只能包含十个 $\sqrt{}$ 运算。
8. 如果 $A$ 是合法表达式，则 $(A)!$ 是合法表达式。（此处的 $!$ 表示阶乘，且表达式 $A$ 的结果必须为非负整数）
9. 如果 $A$ 是合法表达式，则 $-(A)$ 是合法表达式。（此处的 $-$ 表示取负）

现在，Little Mono 想知道表示整数 $N$ 所需的最少 $D$ 的个数。

输入格式

第一行输入包含测试用例的数量 $T$。接下来有 $T$ 个测试用例。 每个测试用例包含一行，由两个整数 $D$ 和 $N$ 组成，分别表示 Little Mono 认识的数字和想要表示的整数。

输出格式

对于每个测试用例，输出一行 “Case #x: y”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 Little Mono 所需的最少 $D$ 的个数。

数据范围

• $1 \le T \le 900$
• $1 \le D \le 9$
• $1 \le N \le 100$

样例

输入 1

3
1 10
4 64
8 50

输出 1

Case #1: 3
Case #2: 2
Case #3: 5

说明

在第一个测试用例中，Little Mono 可以使用 3 个 $1$，通过 $11 - 1$ 来表示 $10$。 在第二个测试用例中，Little Mono 可以使用 2 个 $4$，通过 $\sqrt{\sqrt{4}}^{(4!)}$ 来表示 $64$。