Ishiko 正在开一家手链店。她计划出售的每条手链都表示为一个由 $N$ 颗彩色珠子组成的环，其中恰好有 $K$ 颗由祖母绿制成的绿色珠子，其余 $N-K$ 颗珠子颜色各不相同（既不是绿色，也不与其他任何珠子颜色相同）。对于这 $N - K + 1$ 种不同的颜色，Ishiko 拥有无限数量的珠子供应。

Ishiko 想要展示每一种可能的手链各一个副本。如果两条手链不能通过循环旋转互相重合，则它们被视为不同的手链。例如，左侧的两条手链是不同的，而右侧的两条手链则相同：

供应商接受任意正整数高度的三角形展示柜订单。高度为 $H$ 的展示柜有 $H$ 行，其中第 $i$ 行有 $2*i - 1$ 个槽位，每个槽位可以放置一条手链。例如，下图展示了一个高度为 $3$ 的展示柜，它可以容纳 $1 + 3 + 5 = 9$ 条手链：

Ishiko 需要购买多少个展示柜（高度可以不同），才能在不留下任何空槽位的情况下展示每一种可能的手链各一个副本？

数据范围

• $1 \le T \le 110$
• $1 \le N \le 10^9$
• $0 \le K \le N$
• 所有测试用例中 $N$ 的总和不超过 $8{,}000{,}000{,}000$。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例，输入一行，包含两个由空格分隔的整数 $N$ 和 $K$。

输出格式

对于第 $i$ 个测试用例，输出 "Case #i:"，后跟一个整数，表示 Ishiko 为展示每种手链各一个副本所需购买的展示柜的最少数量。

样例

样例输入

4
5 3
6 3
6 2
243447 42273

样例输出

Case #1: 1
Case #2: 2
Case #3: 4
Case #4: 4

说明

在第一个样例中，假设 Ishiko 的珠子颜色为绿色、蓝色和红色。对于 $N = 5$ 颗珠子且有 $K = 3$ 颗绿色珠子、1 颗红色珠子和 1 颗蓝色珠子的情况，共有 $4$ 种可能的手链（在旋转意义下）：

Ishiko 可以使用一个高度为 $2$ 的展示柜来展示这 $4$ 条手链。

在第二个样例中，假设 Ishiko 的珠子颜色为绿色、蓝色、红色和黄色。对于 $N = 6$ 颗珠子且有 $K = 3$ 颗绿色珠子、1 颗蓝色珠子、1 颗红色珠子和 1 颗黄色珠子的情况，共有 $20$ 种可能的手链。部分示例如下：

如果 Ishiko 购买一个高度为 $2$ 的展示柜和一个高度为 $4$ 的展示柜，她就可以展示这些手链。

在第三个样例中，共有 $60$ 种可能的手链，Ishiko 至少需要 $4$ 个展示柜才能展示所有手链。一种可能的方案是购买两个高度为 $1$ 的展示柜、一个高度为 $3$ 的展示柜和一个高度为 $7$ 的展示柜。