P13376 [GCJ 2011 #2] Expensive Dinner

你的朋友们今晚都要去一家餐厅吃饭。他们都非常擅长数学，但也都很奇怪：你的第 $a$ 个朋友（从 1 开始编号）只有当餐费总额是一个正整数且能被 $a$ 整除时才会感到满意。 你的朋友们会依次进入餐厅。每当有一个人进入餐厅时，如果那个人不满意，那么这群人会立刻叫来一位服务员。 只要餐厅里至少有一个不满意的人，这些不满意的人中就会有一个人购买一份最低价格的食物，使自己变得满意。这个过程会一直持续，直到餐厅里没有人不满意为止，然后服务员才会离开。幸运的是，餐厅出售每一个整数价格的食物。具体例子见第一个样例的解释。 你的朋友们可以以任意顺序进入餐厅。在叫来服务员之后，如果餐厅里有多个人不满意，可以由其中任意一个人先购买食物。所有这些选择的方式可能会影响这群人叫服务员的次数。 作为餐厅老板，你雇佣了一些非常疲惫的服务员。你想要计算你朋友们的“分布值”：他们可能叫服务员的最大次数与最小次数之差。

输入的第一行包含测试用例的数量 $T$。接下来的 $T$ 行，每行包含一个整数 $N$，表示你有多少个朋友。

对于每个测试用例，输出一行，格式为 "Case #$x$: $y$"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是该测试用例的分布值。

**样例解释** 在第 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$。 **数据范围** **小数据集（13 分，测试点 1 - 可见）** - $1 \leq T \leq 100$。 - $1 \leq N \leq 1000$。 - 时间限制：3 秒。 **大数据集（17 分，测试点 2 - 隐藏）** - $1 \leq T \leq 1000$。 - $1 \leq N \leq 10^{12}$。 - 时间限制：6 秒。 由 ChatGPT 4.1 翻译