Orac and Factors

题意翻译

定义 $f(n)$ 为 $n$ 的最小非平凡因子，也就是除了 $1$ 之外的最小因子（本题不讨论非正数因子） 给出两个正整数 $n,k$，你需要进行 $k$ 次操作，每次将 $n$ 加上 $f(n)$（注意这里 $n$ 在每次操作后是会变化的） ### 输入格式 **本题有多组数据** 第一行一个整数 $T$，表示数据组数 接下来 $T$ 行，每行两个整数 $n,k$，表示一组数据 ### 输出格式 对于每组数据，输出一行一个整数，表示 $k$ 次操作后的 $n$ **说明与提示** $1 \le T \le 100$ $1 \le n \le 10^6$，$1 \le k \le 10^9$ $\sum n \le 10^6$ 感谢 @[_Wolverine](https://www.luogu.com.cn/user/120362) 提供的翻译

题目描述

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.

输入输出格式

输入格式

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 $ .

输出格式

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

输入输出样例

输入样例 #1

3
5 1
8 2
3 4

输出样例 #1

10
12
12

说明

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 $ .