今晚有 $n$ 位年轻人要参加 Peter 的篝火晚会。他们决定玩一个由 Titus Flavius Josephus 首次描述的古老的淘汰游戏。以下是该游戏的简要介绍。

在游戏开始前，这些年轻人会围成一个圆圈站在篝火旁，第一个加入圆圈的人将开始游戏。报数将从第一个人开始，并沿圆圈逆时针方向重复进行。也就是说，第一个人开始报一，逆时针方向的第二个人报二，以此类推，直到某个人报到 $k$，该人便离开圆圈成为旁观者。游戏在剩下的人中重复进行，从离开者的逆时针方向的下一个人开始重新报数，并沿相同方向进行，直到所有年轻人都离开了圆圈。

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

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

输入格式

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

对于每个测试用例，唯一的一行包含三个整数 $n, m$ 和 $k$，其中 $1 \le n, m, k \le 10^{18}$ 且 $n \ge m$。

我们保证所有测试用例中 $\min\{m, k\}$（即 $m$ 和 $k$ 的最小值）之和不超过 $2 \times 10^6$。

输出格式

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

样例

输入 1

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

输出 1

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)$ 时，年轻人离开圆圈的顺序。