构造一个简单的数列
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

我们将 f(a,n) 记为这个数列的第 n 项的值，这个数列满足以下几个条件：

1. 数列的第 1 项是 a；

2. 数列任何相邻两个正整数互质；

3. 数列没有任何两项数重复；

4. 在构造这个数列时，如果有多个满足以上条件的数字，则选择最小的。

现在 Foxity 想要考考你，f(a,n) 到底是多少。

输入描述:

这题有多组测试样例

第一行一个整数 ，表示测试样例数，

之后 t 行，每行两个数 ，分别表示数列的首项和需要求的项数

输出描述:

输出 t 行，每行一个整数，为 f(a,n) 的值
示例1

输入

复制 
5
3 1
3 2
3 3
3 4
3 5

输出

复制 
3
1
2
5
4

说明

关于第一组样例第一项为3，其次与3互素的数字且不在{3}中最小的为1，与1互素的数字不在{1,3}中最小的为2，与2互素的数字不在{1,2,3}中最小的为5 ，依次类推