你的朋友们今晚都要去一家餐馆吃晚餐。他们都很擅长数学，但性格都很古怪：你的第 a 个朋友（从 1 开始计数）只有在餐费总额是一个正整数且能被 a 整除时才会感到满意。

你的朋友们会一个接一个地进入餐馆。一旦有人进入餐馆，如果此人感到不满意，该群体会立即呼叫服务员。

只要餐馆里至少有一个人不满意，其中一个不满意的人就会购买能让他或她满意的最低价格的商品。这个过程会一直持续到餐馆里没有人感到不满意为止，然后服务员就会离开。幸运的是，这家餐馆出售各种整数价格的食物。请参阅第一个测试用例的说明以获取示例。

你的朋友们可以选择以任何顺序进入餐馆。在呼叫服务员后，如果餐馆里有不止一个不满意的人，这些不满意的人中的任何一个都可以选择先购买商品。所有这些选择的方式可能会影响群体呼叫服务员的次数。

作为餐馆老板，你雇佣了一些非常疲惫的服务员。你想要计算你朋友们的波动幅度（spread）：他们可能呼叫服务员的最大次数与最小次数之差。

数据范围

小数据集（测试集 1 - 可见；13 分）

$1 \le T \le 100$。

$1 \le N \le 1000$。

大数据集（测试集 2 - 隐藏；17 分）

$1 \le T \le 1000$。

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

样例

输入格式 1

4
1
3
6
16

输出格式 1

Case #1: 0
Case #2: 1
Case #3: 2
Case #4: 5

说明

在用例 #2 中，假设你的朋友按顺序 [1, 2, 3] 到达。首先 #1 到达；他不满意；呼叫服务员；并购买了价格为 1 的商品。现在没有人不满意。接着 #2 到达；他不满意；呼叫服务员；并购买了价格为 1 的商品（总额为 2）。现在没有人不满意。接着 #3 到达；他不满意；呼叫服务员；并购买了价格为 1 的商品（总额为 3）。现在 #2 不满意，购买了价格为 1 的商品（总额为 4）。现在 #3 不满意，购买了价格为 2 的商品（总额为 6）。最终没有人不满意，服务员被呼叫了三次。

假设你的朋友按顺序 [3, 1, 2] 到达。首先 #3 到达；他不满意；呼叫服务员；并购买了价格为 3 的商品。现在没有人不满意。接着 #1 到达；没有人不满意。接着 #2 到达；他不满意；呼叫服务员；并购买了价格为 1 的商品（总额为 4）。现在 #3 不满意，购买了价格为 2 的商品（总额为 6）。现在没有人不满意，服务员被呼叫了两次。波动幅度为 1。