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.*;
import java.math.BigInteger;
import java.util.*;
 
 
 
 
public class Main {
	  int 	getint(BufferedReader sc) throws java.lang.Exception
			{
		//	  String ss=sc.readLine();
		    	int a= Integer.parseInt(sc.readLine());
		    	return a;
			}
		  ArrayList<Integer> getlistint(BufferedReader sc) throws java.lang.Exception
		  {
			  ArrayList<Integer> res=new ArrayList<>();
			  
			  String s=sc.readLine();
			  String[] ss=s.split(" ");
			
			  for(int i=0;i<ss.length;i++)
			  {
				//  String ss=sc.readLine();
			    	int a=Integer.valueOf(ss[i]);
			    	res.add(a);
			  }
		  
			  return res;
		  }
		  ArrayList<Float> getlistfl(BufferedReader sc) throws java.lang.Exception
		  {
			  ArrayList<Float> res=new ArrayList<>();
			  
			  String s=sc.readLine();
			  String[] ss=s.split(" ");
			
			  for(int i=0;i<ss.length;i++)
			  {
				//  String ss=sc.readLine();
			    	float a=Float.valueOf(ss[i]);
			    	res.add(a);
			  }
		  
			  return res;
		  }
		  ArrayList<Long> getlist(BufferedReader sc) throws java.lang.Exception
		  {
			  ArrayList<Long> res=new ArrayList<>();
			  
			  String s=sc.readLine();
			  String[] ss=s.split(" ");
			
			  for(int i=0;i<ss.length;i++)
			  {
				//  String ss=sc.readLine();
			    	long a=Long.valueOf(ss[i]);
			    	res.add(a);
			  }
		  
			  return res;
		  }
		  ArrayList<Character> getlistchar(BufferedReader sc) throws java.lang.Exception
		  {
			  ArrayList<Character> res=new ArrayList<>();
			  
			  String s=sc.readLine();
			//  String[] ss=s.split(" ");
			
			  for(int i=0;i<s.length();i++)
			  {
				//  String ss=sc.readLine();
			    	//char[] a=ss[i].toCharArray();
			    	res.add(s.charAt(i));
			  }
		  
			  return res;
		  }

		  static int n;
		  static int b[];
		  static StringBuffer ans = new StringBuffer("");
		  static BufferedReader bf;
		  static class pair{
		        int a,b;
		        pair(int a,int b){
		            this.a =a;
		            this.b =b;
		        }
		    }private static StringBuilder result = new StringBuilder();

		 
		    public static void main(String[] args) throws Exception 
		    {
		    	Main pra=new Main();
		    	//Scanner sc = new Scanner(System.in);
		      //  int tc;
		    	BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		    //	Scanner in=new Scanner(System.in);
			    long t=Long.parseLong(br.readLine());
		    	
			  // int t=1;
			  while(t-->0){
			    //	int num=Integer.parseInt(br.readLine());
			    //	ArrayList<Integer> p=pra.getlistint(br);
			  ArrayList<Integer> pa=pra.getlistint(br);
			
			  if(pa.get(0)%2==0)
			  {
				  System.out.println(pa.get(0)+2*pa.get(1));
				  continue;
			  }
			  int p = 0;
				for(int i = pa.get(0); i>=2; i--)
					if(pa.get(0)%i==0)
				    	p = i;
				
				System.out.println(pa.get(0)+p+2*(pa.get(1)-1));
		       }
			  // 
		     
		        
		        }
 
}