Orac正在研究数论,他对除数的性质感兴趣。
对于两个正整数 $$$a$$$ 和 $$$b$$$,当且仅当存在整数 $$$c$$$ 时,$$$a$$$ 是 $$$b$$$ 的约数,使得 $$$a\cdot c=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要求你将$$$f(n)$$$添加到$$$n$$$恰好$$$k$$$次(注意$$$n$$$在每次操作后都会改变,所以$$$f(n)$$$也可能改变)并告诉他$$$n$$$的最终值。
例如,如果Orac给你$$$n=5$$$和$$$k=2$$$,首先你应该添加$$$f(5)=5$$$到$$$n=5$$$,这样你的$$$n$$$的新值将等于$$$n=10$$$,之后,你应该添加$$$f(10)=2$$$到$$$10$$$,因此 $$$n$$$ 的新(也是最终!)值将等于 $$$12$$$。
Orac 可能会多次询问您这些问题。
输入
输入的第一行是一个整数 $$$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$$$。
输出
打印 $$$t$$$ 行,其中第 $$$i$$$ 行应包含 Orac 第 $$$i$$$ 查询中 $$$n$$$ 的最终值。
示例
输入 #1
3 5 1 8 2 3 4
输出 #1
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$$$经过一次运算后变为$$$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$$$。