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.
def get_min_divisor(num):
    """
    Finds the minimum divisor of number 'num' that is greater than 1

    Inputs:
    num : <int>
    number for which such a divisor will be found

    Outputs:
    min_divisor: <int>
    The minimum divisor of 'num' that is not 1
    """
    # # Create divisor list consisting of prime numbers using sympy's
    # # primerange() function
    # divisor_list = primerange(2, num)

    # Initialize minimum divisor to the number itself
    min_divisor = num

    # Start with smallest prime divisor that is not 2, 3, or 5,
    # and continue testing divisors until sqrt(num) is reached. Can stop
    # on first divisor found since we are searching for divisors in
    # ascending order. In the event that a divisor is not found by the
    # time sqrt(num) is reached, then smallest divisor that is not 1 is
    # just the number itself.

    max_divisor = int(round(num**0.5, 0))
    for divisor in range(2, max_divisor + 1):
        if num % divisor == 0:
            min_divisor = divisor
            break
    return min_divisor

def update_and_add_minimum_divisor_to_number(num_queries):
    """
    Orac is studying number theory, and he is interested in 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 f(n) as 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, he decided to repeat this operation several
    times.

    Now, for two positive integers n and k, Orac has 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 give you numbers n and k.

    Each of the next t lines contains two positive integers n, k (2≤n≤10^6,
    1≤k≤10^9), separated by a single space, and correspond 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.
    """

    query_number = 0
    # Repeat algorithm until all queries are satisfied
    while query_number < num_queries:
        # get user input data from next line
        addition_data = input()
        # Treat data strings separated by a space as a single element
        addition_data_list = addition_data.split(" ")
        # Extract elements representing the number to be divisor'd and the
        # number of times the updated number should be added to its new min
        # divisor
        number = int(addition_data_list[0])
        total_additions = int(addition_data_list[1])

        # Reset number of additions for each query
        remaining_additions = total_additions
        # Repeat process until 'total_additions' additions have been made
        while remaining_additions > 0:
            # Find the minimum divisor of the current number
            min_divisor = get_min_divisor(number)
            # If the number is divisible by 2, then the minimum remainder
            # will always be 2 and we can just add the product of 2 and the
            # remaining number of additions to the current number
            if min_divisor == 2:
                number += 2*remaining_additions
                break
            else:
                # Continue as normal
                # Add min divisor to the current number
                number += min_divisor
            # Continue process until number of additions
            remaining_additions -= 1

        # Print the result of the algorithm for the query just completed
        print(number)
        query_number += 1


num_queries_user = int(input())
update_and_add_minimum_divisor_to_number(num_queries_user)
# Example
# inputCopy
# 3
# 5 1
# 8 2
# 3 4
# outputCopy
# 10
# 12
# 12