题目描述

每个测试的时间限制：2 秒
每个测试的内存限制：256 兆字节

Orac 正在研究数论，他对因数的性质很感兴趣。

对于两个正整数 $a$ 和 $b$，如果存在整数 $c$ 使得 $a \cdot c = b$，则称 $a$ 是 $b$ 的因数。

对于 $n \ge 2$，我们记 $f(n)$ 为 $n$ 的最小正因数（除了 $1$ 以外）。

例如：$f(7) = 7$，$f(10) = 2$，$f(35) = 5$。

对于给定的整数 $n$，Orac 决定将 $f(n)$ 加到 $n$ 上。

例如，如果他有 $n = 5$，那么新的 $n$ 将变为 $10$。如果他有 $n = 6$，那么 $n$ 将变为 $8$。

Orac 非常喜欢这个过程，所以他决定重复这个操作多次。

现在，对于两个正整数 $n$ 和 $k$，Orac 要求你恰好执行 $k$ 次操作：每次将 $f(n)$ 加到当前的 $n$ 上（注意 $n$ 在每次操作后会变化，因此 $f(n)$ 也可能变化），然后告诉他 $n$ 的最终值。

例如，如果 Orac 给你 $n = 5$ 和 $k = 2$，首先将 $f(5) = 5$ 加到 $5$ 上，得到 $n = 10$；然后加上 $f(10) = 2$，得到最终值 $n = 12$。

Orac 可能会多次询问你。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 100$）—— 询问的次数。

接下来的 $t$ 行，每行包含两个正整数 $n, k$（$2 \le n \le 10^6$，$1 \le k \le 10^9$），对应 Orac 的一个询问。

保证所有询问的 $n$ 之和不超过 $10^6$。

输出格式

输出 $t$ 行，其中第 $i$ 行应包含第 $i$ 个询问中 $n$ 的最终值。

3
5 1
8 2
3 4

10
12
12

说明

• 第一个询问：$n = 5$，$k = 1$。$5$ 的因数为 $1$ 和 $5$，除了 $1$ 以外的最小因数为 $5$。因此操作将 $f(5) = 5$ 加到 $5$，结果为 $10$。
• 第二个询问：$n = 8$，$k = 2$。$8$ 的因数为 $1,2,4,8$，除了 $1$ 以外的最小因数为 $2$。第一次操作后 $8$ 变为 $10$。$10$ 的因数为 $1,2,5,10$，除了 $1$ 以外的最小因数为 $2$。第二次操作后变为 $12$。
• 第三个询问：$n$ 的变化过程为：$3 \rightarrow 6 \rightarrow 8 \rightarrow 10 \rightarrow 12$。