449 人解决，541 人已尝试。
565 份提交通过，共有 1433 份提交。
1.8 EMB 奖励。
单点时限: 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
449 人解决，541 人已尝试。
565 份提交通过，共有 1433 份提交。
1.8 EMB 奖励。