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 math
t = int(input())
def solve(n):
    sqr = math.floor(math.sqrt(n))
    for i in range(3, sqr+1, 2):
        if n % i == 0:
            return i
    return n
    



while t:
    n, k = map(int,(input().split()))
    ans = 0
    if n % 2==0:
        ans = n + k*2
    if n % 2==1:
        ans = n + 2*(k-1) + solve(n)
    print(ans)
    t-=1


















'''def find_gcd(x, y): 
    while(y): 
        x, y = y, x % y 
  
    return x
def lcm(a,b): 
    return (a*b) / find_gcd(a,b)
def solve(lst):
    
    

    


    l = []
    for i in range(len(lst)):
        for j in range(i+1, len(lst)):
            l.append(int(lcm(lst[i],lst[j])))
    #print("list", l)
    if len(l) == 1:
        return l[0]
    num1=l[0] 
    num2=l[1] 
    gcd=find_gcd(num1,num2) 
  
    for i in range(2,len(l)): 
        gcd=find_gcd(gcd,l[i])
    return int(gcd)

n = int(input())
lst = list(map(int, input().split()))
print(solve(lst))

'''




'''t = int(input())
while(t):
    n, k = map(int, input().split())
    a = k%(n-1)
    b = k//(n-1)
    c = n*b
    if a == 0:
        res = c - 1
    else:
        res = c + a
    
    #print(a, b, c)
    print(res)
    
    t-=1



'''



















'''t = int(input())
while t:
    n = int(input())
    count = 0
    lst = []
    a = len(str(n))
    while a:
        
        b = n//(10**(a-1))
        #print(a, b)
        if b != 0:
            lst.append(b*(10**(a-1)))
            n = n - lst[-1]
            count += 1
            #print(n, count, lst)
        
        a -= 1

    print(count)
    print(*lst)
    t -= 1
'''
