CF1350A.Orac and Factors

Orac is studying number theory, and he is interested in the properties of divisors.

For two positive integers $a$ and $b$, $a$ is a divisor of $b$ if and only if there exists an integer $c$, such that $a\cdot c=b$.

For $n \ge 2$, we will denote as $f(n)$ the smallest positive divisor of $n$, except $1$.

For example, $f(7)=7,f(10)=2,f(35)=5$.

For the fixed integer $n$, Orac decided to add $f(n)$ to $n$.

For example, if he had an integer $n=5$, the new value of $n$ will be equal to $10$. And if he had an integer $n=6$, $n$ will be changed to $8$.

Orac loved it so much, so he decided to repeat this operation several times.

Now, for two positive integers $n$ and $k$, Orac asked you to add $f(n)$ to $n$ exactly $k$ times (note that $n$ will change after each operation, so $f(n)$ may change too) and tell him the final value of $n$.

For example, if Orac gives you $n=5$ and $k=2$, at first you should add $f(5)=5$ to $n=5$, so your new value of $n$ will be equal to $n=10$, after that, you should add $f(10)=2$ to $10$, so your new (and the final!) value of $n$ will be equal to $12$.

Orac may ask you these queries many times.

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 要求你对 $n$ 恰好执行 $k$ 次上述操作（注意：每次操作后 $n$ 的值都会改变，因此 $f(n)$ 也可能随之改变），并告诉他最终的 $n$ 值。

例如，若 Orac 给出 $n=5$ 和 $k=2$，首先你应将 $f(5)=5$ 加到 $n=5$ 上，得到新的 $n=10$；接着，你应将 $f(10)=2$ 加到 $10$ 上，从而得到新的（也是最终的！）$n$ 值为 $12$。

Orac 可能会多次向你提出此类查询。

The first line of the input is a single integer $t\ (1\le t\le 100)$: the number of times that Orac will ask you.

Each of the next $t$ lines contains two positive integers $n,k\ (2\le n\le 10^6, 1\le k\le 10^9)$, corresponding to a query by Orac.

It is guaranteed that the total sum of $n$ is at most $10^6$.

输入的第一行是一个整数 $t\ (1\le t\le 100)$：表示 Orac 向你提问的次数。

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

保证所有查询中 $n$ 的总和不超过 $10^6$。

Print $t$ lines, the $i$-th of them should contain the final value of $n$ in the $i$-th query by Orac.

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

In the first query, $n=5$ and $k=1$. The divisors of $5$ are $1$ and $5$, the smallest one except $1$ is $5$. Therefore, the only operation adds $f(5)=5$ to $5$, and the result is $10$.

In the second query, $n=8$ and $k=2$. The divisors of $8$ are $1,2,4,8$, where the smallest one except $1$ is $2$, then after one operation $8$ turns into $8+(f(8)=2)=10$. The divisors of $10$ are $1,2,5,10$, where the smallest one except $1$ is $2$, therefore the answer is $10+(f(10)=2)=12$.

In the third query, $n$ is changed as follows: $3 \to 6 \to 8 \to 10 \to 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$ 变为 $8+(f(8)=2)=10$。$10$ 的因数为 $1,2,5,10$，其中除 $1$ 外最小的因数是 $2$，故答案为 $10+(f(10)=2)=12$。

在第三次查询中，$n$ 的变化过程如下：$3 \to 6 \to 8 \to 10 \to 12$。