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⋅ c=b.

For n ≥ 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

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

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

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

Output

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

Example

Input


3
5 1
8 2
3 4


Output


10
12
12

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 → 6 → 8 → 10 → 12.
#                                               |
#   _` |  __ \    _` |   __|   _ \   __ \    _` |   _` |
#  (   |  |   |  (   |  (     (   |  |   |  (   |  (   |
# \__,_| _|  _| \__,_| \___| \___/  _|  _| \__,_| \__,_|

import sys
import math

def read_line():
	return sys.stdin.readline()[:-1]
 
def read_int():
	return int(sys.stdin.readline())
	
def read_int_line():
	return [int(v) for v in sys.stdin.readline().split()]

def read_float_line():
	return [float(v) for v in sys.stdin.readline().split()]

# def SieveOfEratosthenes(n): 
      
#     # Create a boolean array "prime[0..n]" and initialize 
#     #  all entries it as true. A value in prime[i] will 
#     # finally be false if i is Not a prime, else true. 
#     prime = [True for i in range(n+1)] 
#     p = 2
#     while (p * p <= n): 
          
#         # If prime[p] is not changed, then it is a prime 
#         if (prime[p] == True): 
              
#             # Update all multiples of p 
#             for i in range(p * p, n+1, p): 
#                 prime[i] = False
#         p += 1
      
#     ls = []
#     # Print all prime numbers 
#     for p in range(2, n+1): 
#         if prime[p]: 
#             ls.append(p)
#     return ls

# t = read_int()
# for i in range(t):
# 	n = read_int()
# 	g = SieveOfEratosthenes(n)
# 	a = read_int_line()
# 	ans = 1

# 	for i in g:
# 		cur = 1
# 		if a[0]<a[i-1]:
# 			cur +=1
# 		k = i*2
# 		ptr = 2

# 		while k<=n:
# 			if a[i-1]<a[k-1]:
# 				cur+=1
# 			ptr +=1
# 			k = i*ptr
# 		ans = max(cur,ans)
# 	print(ans)

def smallestDivisor(n): 
  
    # if divisible by 2 
    if (n % 2 == 0): 
        return 2; 
  
    # iterate from 3 to sqrt(n) 
    i = 3;  
    while(i * i <= n): 
        if (n % i == 0): 
            return i; 
        i += 2; 
  
    return n;

t = read_int()
for i in range(t):
	n,k = read_int_line()
	if n&1==1:
		n = n + smallestDivisor(n)
		if k>1:
			k-=1
			n += 2*k
	else:
		n = n + 2*k

	print(n)