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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
 
/* Name of the class has to be "Main" only if the class is public. */
public class Codechef
{
    static int isPrime(int n){
        boolean[] prime=new boolean[n+1];
        for(int i=0;i<=n;i++)prime[i]=true;
        prime[0] = prime[1] = false;
        for (int i = 2; i * i <= n; i++) {
         if (prime[i]) {
         for (int j = i * i; j <= n; j += i)
            prime[j] = false;
         }
        }
        for(int i=3;i*i<=n;i+=2){
            if(n%i==0)return i;
        }
        return n;
   }
	public static void main (String[] args) throws java.lang.Exception
	{
		FastReader s = new FastReader();
		PrintWriter pw = new PrintWriter(System.out);
        int t=s.nextInt();
        while(t-->0){
            int n=s.nextInt();
            long k=s.nextLong();
            int h=0;
            if(n%2==0)h=2;
            else{h=isPrime(n);}
            System.out.println((long)n+(long)h+(2*(k-1)));
        }
	}
}
class FastReader {
	BufferedReader br;
	StringTokenizer st;
 
	public FastReader() {
		br = new BufferedReader(new
		                        InputStreamReader(System.in));
	}
 
	String next() {
		while (st == null || !st.hasMoreElements()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (IOException  e) {
				e.printStackTrace();
			}
		}
		return st.nextToken();
	}
 
	int nextInt() {
		return Integer.parseInt(next());
	}
 
	long nextLong() {
		return Long.parseLong(next());
	}
 
	double nextDouble() {
		return Double.parseDouble(next());
	}
 
	String nextLine() {
		String str = "";
		try {
			str = br.readLine();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return str;
	}
}
