3027. 抽奖

单点时限: 2.0 sec

内存限制: 256 MB

现有一抽奖活动,参加抽奖的员工已经按照报名先后顺序进行了编号(编号从 开始)。抽奖办法如下:由一位特邀嘉宾随机抽取两个正整数 ,然后将与整数 互素(互质)的员工编号按从小到大排成数列,这个数列中的第 项就是本次活动的特等奖获得者。

例如,

则与 互素的递增数列为:

这个数列中第 项为 ,则编号为 的员工为本次活动的特等奖获得者。

请编写一程序实现上述功能。

输入格式

行:一个整数 () 为问题数。

接下来有 行,对应每个问题有 行,每行有两个由一个空格分隔的正整数

输出格式

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

然后对应每个问题在一行中输出那个特等奖获得者编号。

样例

Input
3
20 7
105 1000
98 3666
Output
case #0:
17
case #1:
2186
case #2:
8553

270 人解决,334 人已尝试。

334 份提交通过,共有 698 份提交。

2.1 EMB 奖励。

创建: 5 年,7 月前.

修改: 1 年,3 月前.

最后提交: 1 月,1 周前.

来源: 2014年编程实践课程第二次上机考试

题目标签