F. Moon loves Mel (Purple)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Donatello and Moon are working in their lab down in the sewers to synthesize a new chemical agent called Mel! It is Moon's favorite.

The Mel starts with an initial power level of $$$X$$$.

Donatello and Moon after realising the power of Mel.

In a single reaction step, Donatello's and Moon machine takes the smallest prime factor of the current power level and adds it to the total. This reaction process is repeated exactly $$$K$$$ times.

Note: If the power level is prime, its smallest prime factor is itself

Calculate the final Mel power level!

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — denotes the number of test cases.

For each test case, the only line of the test case with two space-separated numbers $$$X$$$ and $$$K$$$ ($$$2 \le X \le 10^9$$$ and $$$1 \le K \le 10^9$$$) — denotes the initial power level of Mel and the number of times the reaction process is repeated, respectively.

Output

For each test case print the final power level of Mel after exactly $$$K$$$ steps.

Example
Input
4
10 3
15 4
17 2
21 5
Output
16
24
36
32