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-----

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-----

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 \to 6 \to 8 \to 10 \to 12$.

Difficulty: interview

Starter code:

Solutions:
import sys
input = sys.stdin.readline

def mult_input():
	return map(int,input().split())

def list_input():
	return list(map(int,input().split()))

for nt in range(int(input())):
	n,k=map(int,input().split())
	for i in range(2,n+1):
		if n%i==0:
			num=i
			break
	print (n+i+2*(k-1))

t=int(input())
for _ in range(t):
    n,k=list(map(int,input().split()))
    if n%2==0:
        print(n+2*k)
    else:
        i=2
        while 1>0:
            if n%i==0:
                break
            i=i+1
        n=n+i
        k=k-1
        print(n+2*k)

t = int(input())
for ii in range(t):
    n, k = map(int, input().split())
    if n % 2 == 0:
        print(n + 2 * k)
    else:
        f = 0
        for j in range(2, n + 1):
            if n % j == 0:
                print(n + j + 2 * (k - 1))
                break

'''input
3
5 1
8 2
3 4
'''
def solve():
	n,k = map(int,input().split())
	div = 0
	for i in range(2,n+1):
		if n%i==0:
			div = i
			break
	print(n+div+(k-1)*2)
	return 
t = 1
t = int(input())
while t>0:
	t-=1
	solve()

q = int(input())

for _ in range(q):
    n, k = list(map(int, input().split()))
    if n%2:
        for d in range(3, n+1):
            if n%d == 0:
                n += d
                k -= 1
                break
    n += k*2
    print(n)


import sys

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')


def solve():
    n, k = nm()
    for i in range(2, n+1):
        if n % i == 0:
            n += i
            break
    n += 2 * (k-1)
    print(n)
    return

# solve()

T = ni()
for _ in range(T):
    solve()


for _ in range(int(input())):
    n, k = map(int, input().split())
    d1 = 2
    while n % d1 != 0:
        d1 += 1

    n = n + d1
    k -= 1
    n += k*2
    print(n)

# The real secret to success is enthusiasm. Walter Chrysler
# by : Blue Edge - Create some chaos

def give(n):
    i=2
    while i*i<=n:
        if n%i==0:
            return i
        i+=1
    return n
for _ in range(int(input())):
    n,k=list(map(int,input().split()))
    print(n+give(n)+2*(k-1))


t=int(input())
for i in range(t):
  n,k=map(int,input().split())
  ans=n
  for i in range(2,n+1):
    if n%i==0:
      ans+=i
      break
  ans+=2*(k-1)
  print(ans)

for f in range(int(input())):
    n,k=map(int,input().split())
    div=2
    while div*div<n and n%div!=0:
        div+=1
    if div*div>n:
        div=n
    print(n+div+(k-1)*2)

"""T=int(input())
for _ in range(0,T):
    n=int(input())
    a,b=map(int,input().split())
    s=input()
    s=[int(x) for x in input().split()]
    for i in range(0,len(s)):
        a,b=map(int,input().split())"""


T=int(input())
for _ in range(0,T):
    n,k=list(map(int,input().split()))
    ans=n
    if(n%2==0):
        ans+=(2*k)
    else:
        ans+=(2*(k-1))
        for i in range(2,n+1):
            if(n%i==0):
                ans+=i
                break
    print(ans)
    


t = int(input())
for _ in range(t):
    n, k = list(map(int, input().split()))
    best = 0
    for i in range(2, n+1):
        if n % i == 0:
            best = i
            break
    print(n+best+(2*(k-1)))



from math import sqrt
from collections import defaultdict as dd
import sys
input=sys.stdin.readline
import bisect
t=int(input())
while t:
    #n=int(input())
    n,k=map(int,input().split())
    #l=list(map(int,input().split()))
    for i in range(2,n+1):
        if(n%i==0):
            ind=i
            break
    n=n+i
    n=(k-1)*2+n
    print(n)
    t-=1

# test = iter('''0
# 1 2
# '''.splitlines())
#
#
# def input():
#     return next(test)


def int_input():
    return int(input())


def ints_input():
    return (int(x) for x in input().split())


t=int_input()
for _ in range(t):
    n,k=ints_input()
    if (n&1) == 0:
        print(n+k+k)
    else:
        for i in range(3, n+1, 2):
            if n % i == 0:
                print(n+i+2*(k-1))
                break

t = int(input())

for _ in range(t):
    n, k = list(map(int, input().strip().split()))
    if n % 2 == 0:
        print(n + 2*k)
    else:
        for i in range(3, n + 1):
            if n % i == 0:
                print(n + i + (k-1)*2)
                break

import math
import sys

#sys.stdin = open("in.txt")

t = int(input())
for i in range(t):
    n, k = map(int, input().split())
    for i in range(k):
        if  (n % 2 == 0):
            n += 2 * (k - i)
            break
        else:
            for d in range(3, 1000, 2):
                if (n % d == 0 or d * d > n):
                    break
            if (n % d > 0):
                d = n
            n += d
    print(n)

#  =========     /\       /|    |====/|
#      |        /  \       |    |   / |
#      |       /____\      |    |  /  |
#      |      /      \     |    | /   |
#  ========= /        \  =====  |/====|  
#  code

def main():
    from math import sqrt
    t = 1
    t = int(input())
    for _ in range(t):
        n , k = map(int , input().split())
        if n % 2 == 0:
            print(n + k * 2)
        else:
            for i in range(3 , n + 1):
                if n % i == 0:
                    print(n + i + (k - 1) * 2)
                    break
    return

def __starting_point():
    main()
__starting_point()

t=int(input())
for you in range(t):
    l=input().split()
    n=int(l[0])
    k=int(l[1])
    for i in range(2,n+1):
        if(n%i==0):
            break
    n+=i
    k-=1
    print(n+(2*k))


for i in range(int(input())):
    n,k=map(int,input().split())
    ind=-1
    for j in range(2,int(n**0.5)+1):
        if n%j==0:
            ind=j
            break
    if ind==-1:
        ind=n
    k-=1
    su=n+ind+(k)*2
    print(su)

t=int(input())
for _ in range(t):
	n,k=list(map(int,input().split()))
	div=-1
	for i in range(2,int(n*0.5)+1):
		if n%i==0:
			div=i
			break
	if div==-1:
		div=n
	n+=div
	k-=1
	print(n+k*2)