程序设计能力实训

1084. 天黑请闭眼

单点时限: 2.0 sec

内存限制: 256 MB

“ 天黑请闭眼 ” 游戏 中,有四个角色:上帝、杀手、警察、橡皮假人,游戏规则是杀手若将警察杀死则杀手获胜。

现假设一局游戏中除杀手外,还有 n 个人,而这 n 个人中只有一个警察,剩下 n-1 个都是橡皮假人。杀手按照一定的规律杀人,他将这 n 个人围成一圈进行编号 (1,2,3,…,n),从第一个人开始,顺时针方向数到第 m 个人就将他杀掉,然后再从下一个人开始数到第 m 个人作为被杀对象,以此循环杀人。上帝知道了这个规律,为了保护警察,需要将警察放到最安全的位置(也就是最后一个被杀的位置)。现在你是上帝,请编写程序找到这个最安全的位置。

输入格式

第 1 行:一个整数 T(1≤T≤10)为问题数。

第 2~T+1 行: 对应每个问题有一行, 每行有两个整数 n, m,两个整数之间有一个空格。

$1 \le n, m \le 1000$

输出格式

对于每个问题,输出一行问题的编号(0 开始编号,格式:case #0: 等)

然后对应每个问题在一行中输出 警察的位置(最安全的位置)。

样例

Input
3
7 4
68 34
999 333
Output
case #0:
2
case #1:
13
case #2:
619
不限期开放

题目列表