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 java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        AOracAndFactors solver = new AOracAndFactors();
        solver.solve(1, in, out);
        out.close();
    }

    static class AOracAndFactors {
        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            int t = in.scanInt();
            while (t-- > 0) {
                int n = in.scanInt();
                int k = in.scanInt();

                if (n % 2 == 0) {
                    out.println(n + (k * 2l));
                } else {
                    while ((n % 2 != 0) && k > 0) {
                        int index = -1;
                        for (int i = 2; i * i <= n; i++) {
                            if (n % i == 0) {
                                index = i;
                                break;
                            }
                        }
                        if (index == -1) index = n;
                        n += index;
                        k--;
                    }

                    out.println(n + (k * 2l));
                }
            }
        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int INDEX;
        private BufferedInputStream in;
        private int TOTAL;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (INDEX >= TOTAL) {
                INDEX = 0;
                try {
                    TOTAL = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (TOTAL <= 0) return -1;
            }
            return buf[INDEX++];
        }

        public int scanInt() {
            int I = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    I *= 10;
                    I += n - '0';
                    n = scan();
                }
            }
            return neg * I;
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

    }
}

