单点时限: 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:
等)。
然后对应每个问题在一行中输出那个特等奖获得者编号。
3 20 7 105 1000 98 3666
case #0: 17 case #1: 2186 case #2: 8553