互质指的是两个整数的最大公约数为 1。给定 n，编程计算与它互质的第 k大的整数。
第一行为整数 t(≤10),表示数据组数；接下来 t 行，每行两个正整数 n(≤10^6 ￥)和 k(≤10^8$ )。
对于每组数据，输出与 n 互质的第 k 大的正整数。
2 2017 10 30030 100000
10 521351