程序设计能力实训

1193. 抽奖

单点时限: 2.0 sec

内存限制: 256 MB

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

例如,$m=6$,$n=9$

则与 $m$ 互素的递增数列为:$1,5,7,11,13,17,19,23,25,29,…,$

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

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

输入格式

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

接下来有 $T$ 行,对应每个问题有 $1$ 行,每行有两个由一个空格分隔的正整数 $m,n (1≤m,n≤50000)$。

输出格式

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

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

样例

Input
3
20 7
105 1000
98 3666
Output
case #0:
17
case #1:
2186
case #2:
8553
不限期开放

题目列表