Orac and Factors
Contest: Codeforces Round 641 (Div. 2)
Difficulty rating: 900
Tags: math

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.

Input format:
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$$$.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
3
5 1
8 2
3 4

Example output:
10
12
12

Editorial:
If we simulate the whole process we will get TLE because $$$k$$$ is too large. So we need some trivial observations:
• If $$$n$$$ is even, then for each operation $$$n$$$ will be added by $$$2$$$ and keep being even.
• If $$$n$$$ is odd, then for the first time $$$n$$$ will be added by an odd number and then become even.
So it's easy to see that the answer is $$$$$$ \left\{ \begin{array}{lcl} n+2k & n\textrm{ is even}\\ n+2(k-1)+d(n) & n\textrm{ is odd}\\ \end{array} \right. $$$$$$ where $$$d(n)$$$ is the smallest positive factor of $$$x$$$ except $$$1$$$, which can be calculated in $$$O(n)$$$ time.
The overall complexity is $$$O(n)$$$ .