题解

本题要求找出第 k 个不是 n 的因子的正整数。给定正整数 n，其因子满足一定的规律。我们可以先求出 n 的所有因子，然后利用因子之间的间隔计算出哪些区间内的数字为非因子。具体来说，对于任意一个正整数 x，如果在区间 [1, x] 中 n 的因子个数为 i，那么区间内非因子个数为 x - i。当 x - i 大于等于 k 时，说明第 k 个非因子出现在区间 [1, x] 内，可以直接通过数学关系求出答案。

本题代码采用如下思路：

1. 求 n 的因子
   遍历 1 至 √n，若 x 为 n 的因子，则将 x 和 n//x 加入因子列表（注意去重），最后对因子列表进行排序。

2. 利用因子间隔确定答案
   用变量 i 表示遍历到当前的因子数量，对于每个因子 f，区间 [1, f] 内非因子个数为 f - i。如果 f - i ≥ k，则说明第 k 个非因子在 f 之前，可以通过 i+k-1 得到答案；否则继续遍历所有因子。当所有因子遍历完后，说明答案落在 n 之后，此时直接返回 i+k。

题目内容

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

例如，当$n=6$时：$6$的因子有：$1,2,3,6$,不是$6$的因子数依次为：$4,5,7,8,9,10,......$。如果$k=2$，答案就是$5$（第二个不是$6$的因子的数）

输入描述

第一行输入一个整数$t$,表示测试用例数。

接下来$t$行，每行包含两个整数$n$和$k$。

$1≤t≤1000$

1≤n,k≤10^9

输出描述

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

样例1

输入

2
6 2
6 10

输出

5
14