题目描述

薯条哥有一个正整数$n$，她想找出第$k$个不是$n$的因子的正整数。

例如，当$n = 6$ 时：$6$ 的因子有：$1, 2, 3, 6$，不是$6$的因子的数依次为：$4, 5, 7, 8, 9, 10$, ……。

如果 $k = 2$，答案就是$5$（第二个不是$6$的因子的数）

输入描述

第一行输入一个整数$t(1\le t\le 1000)$，表示测试用例数。

接下来$t$行，每行包含两个整数$n,k(1\le n,k\le 10^9)$。

输出描述

对于每个测试用例，输出一个整数，表示第$k$个不是$n$的因子的正整数。

样例

输入

2
6 2
6 10

输出

5
14