题目描述

今晚，$n$ 名年轻男子将参加彼得的篝火晚会。他们决定玩一个古老的数数出局游戏，该游戏最早由提图斯·弗拉维奥·约瑟夫斯（Titus Flavius Josephus）描述。以下是游戏的简要介绍。

游戏开始前，这些年轻人将围绕篝火站成一个圆圈，第一个加入圆圈的人将开始游戏。计数将从第一个人开始，并沿逆时针方向反复绕圈进行。即第一个人报 $1$，逆时针方向第二个人报 $2$，依此类推，直到某个不幸的人报到 $k$ 并因此离开圆圈成为旁观者。游戏将在剩下的人中重复进行，从出局者沿逆时针方向的下一个人作为新的第一个人重新开始，方向不变，直到所有年轻人都离开圆圈。

彼得想成为第 $m$ 个离开圆圈的人，因为他坚信这个数字对他来说是幸运的。作为一名熟练的程序员，你能否指出他在游戏开始前应该站的位置，以便实现他的目标？

为清晰起见，我们假设第一个加入圆圈的人的编号为 $1$，沿其逆时针方向下一个人的编号为 $2$，依此类推。按照定义，该方向上的最后一个人的编号应为 $n$，你的任务是确定彼得想要位置所对应的编号。

输入格式

输入包含多个测试用例，第一行包含一个正整数 $T$ 表示测试用例的数量，最多不超过 $1000$。

对于每个测试用例，仅有一行包含三个整数 $n$、$m$ 和 $k$，满足 $1 \le n, m, k \le 10^{18}$ 且 $n \ge m$。我们保证所有测试用例中 $\min \lbrace m, k \rbrace$ （即 $m$ 和 $k$ 的最小值）之和不超过 $2 \times 10^6$。

输出格式

对于每个测试用例，输出一行 "Case #x: y"（不含引号），其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是正确位置的编号。

20
10 1 2
10 2 2
10 3 2
10 4 2
10 5 2
10 6 2
10 7 2
10 8 2
10 9 2
10 10 2
10 1 3
10 2 3
10 3 3
10 4 3
10 5 3
10 6 3
10 7 3
10 8 3
10 9 3
10 10 3

Case #1: 2
Case #2: 4
Case #3: 6
Case #4: 8
Case #5: 10
Case #6: 3
Case #7: 7
Case #8: 1
Case #9: 9
Case #10: 5
Case #11: 3
Case #12: 6
Case #13: 9
Case #14: 2
Case #15: 7
Case #16: 1
Case #17: 8
Case #18: 5
Case #19: 10
Case #20: 4

提示

样例实际上展示了当 $(n, k)$ 分别设定为 $(10, 2)$ 和 $(10, 3)$ 时，年轻人离开圆圈的顺序。

翻译由 DeepSeek V4 Pro 完成