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 io
import os
import sys
from atexit import register
import random
import math
import itertools

##################################### Flags          #####################################
# DEBUG = True
DEBUG = False
STRESSTEST = False

##################################### IO             #####################################

if not DEBUG:
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
sys.stdout = io.BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))

tokens = []
tokens_next = 0


def nextStr():
    global tokens, tokens_next
    while tokens_next >= len(tokens):
        tokens = input().split()
        tokens_next = 0
    tokens_next += 1

    if type(tokens[tokens_next - 1]) == str:
        return tokens[tokens_next - 1]
    return tokens[tokens_next - 1].decode()


def nextInt():
    return int(nextStr())


def nextIntArr(n):
    return [nextInt() for i in range(n)]


def print(*argv, end='\n'):
    for arg in argv:
        sys.stdout.write((str(arg) + ' ').encode())
    sys.stdout.write(end.encode())


##################################### Helper Methods #####################################
def genTestCase():
    raise NotImplementedError


def bruteforce(n, k):
    for _ in range(k):
        n += next(i for i in range(2, n + 1) if n % i == 0)
    return n


def doStressTest():
    while True:
        curTest = genTestCase()
        mySoln = solve(curTest)
        bruteforceSoln = bruteforce(curTest)
        if mySoln != bruteforceSoln:
            print('### Found case ###')
            print(curTest)
            print(f'{mySoln} should have been: {bruteforceSoln}')
            return


def solve(n, k):
    def f(n):
        return next((i for i in range(2, int(n**0.5) + 10) if n % i == 0), n)

    while f(n) > 2:
        n += f(n)
        k -= 1
    return n + k * f(n)


##################################### Driver         #####################################

if __name__ == "__main__":
    if not DEBUG and STRESSTEST:
        raise Exception('Wrong flags!')

    if STRESSTEST:
        doStressTest()
    else:
        ### Read input here
        t = nextInt()
        for _ in range(t):
            n = nextInt()
            k = nextInt()
            print(solve(n, k))

    sys.stdout.flush()