Description

某间洗手间有 $N + 2$ 个隔间排成一排，最左端和最右端的隔间被洗手间管理员永久占用。其余 $N$ 个隔间供用户使用。

每当有人进入洗手间时，他们会尽量选择距离其他人最远的隔间。为避免混淆，他们遵循如下确定性规则：对于每一个空隔间 $S$，计算两个值 $L_S$ 和 $R_S$，分别表示 $S$ 到其左侧最近被占用隔间之间的空隔间数，以及到其右侧最近被占用隔间之间的空隔间数。然后，他们会考虑那些最近邻距离最远的隔间，即使得 $\min(L_S, R_S)$ 最大的所有 $S$。如果只有一个这样的隔间，则选择它；否则，在这些隔间中选择 $\max(L_S, R_S)$ 最大的那个。如果仍有多个隔间并列，则选择这些隔间中最靠左的一个。

有 $K$ 个人即将依次进入洗手间；每个人都会在下一个人到来前选择好自己的隔间。没有人会离开。

当最后一个人选择隔间 $S$ 时，对于他所选隔间，$\max(L_S, R_S)$ 和 $\min(L_S, R_S)$ 的值分别是多少？

Input Format

输入的第一行为测试用例数 $T$。接下来的 $T$ 行，每行描述一个测试用例，包含两个整数 $N$ 和 $K$，含义如上所述。

Output Format

对于每个测试用例，输出一行，格式为 Case #x: y z，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为最后一个人选择的隔间 $S$ 的 $\max(L_S, R_S)$，$z$ 为 $\min(L_S, R_S)$。

5
4 2
5 2
6 2
1000 1000
1000 1

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

Hint

样例解释

在样例 1 中，第一个人占据了中间两个隔间中最左边的一个，剩下的状态为（O 表示已占用，. 表示空）：O.O..O。然后，第二个人（也是最后一个人）占据了紧挨着右侧的隔间，此时一侧有 1 个空隔间，另一侧没有空隔间。

在样例 2 中，第一个人占据了中间的隔间，状态变为 O..O..O。然后，第二个人占据了最左边的隔间。

在样例 3 中，第一个人占据了两个中间隔间中最左边的一个，状态为 O..O...O。第二个人随后占据了连续三个空隔间中间的那个。

在样例 4 中，最后所有隔间都被占满，无论选择顺序如何。

在样例 5 中，唯一一个人选择了最左边的中间隔间。

数据范围

• $1 \leq T \leq 100$。
• $1 \leq K \leq N$。

小数据集 1（5 分，测试点 1 - 可见）

• $1 \leq N \leq 1000$。

小数据集 2（10 分，测试点 2 - 可见）

• $1 \leq N \leq 10^{6}$。

大数据集（15 分，测试点 3 - 隐藏）

• $1 \leq N \leq 10^{18}$。

由 ChatGPT 4.1 翻译