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.util.*;
import java.io.*;
public class Main
{
    static PrintWriter out;
    
    
	static class FastReader{
		BufferedReader br;
		StringTokenizer st;
		public FastReader(){
			br=new BufferedReader(new InputStreamReader(System.in));
			out=new PrintWriter(System.out);
		}
		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;
		}
	}
    
    public static int no(int n)
    {
        if(n>=1 && n<=9)
        {
            return 1 ;
        }
        
        
        return no(n/10) + 1 ;
    }
    
    public static long help(long n)
    {
        for(long i = 3; i <= n ; i++)
        {
            if(n% i == 0) return i ;
        }
        
        return 2 ;
    }
    
    
     
     public static long sol(long n , long k )
     {
        if(k == 1)
        {
          return  help(n) + n ; 
        }
        
        long ans = sol(help(n) + n , k-1 ) ;
        
        return ans  ;
         
     }
     
     
     
    public static void main(String[] args)
    {
       FastReader scn = new FastReader();
      
      int t = scn.nextInt() ;
      
      for( int m = 1; m<=  t; m++){
       long n,k;
       n = scn.nextLong() ;
       k = scn.nextLong() ;
        
        StringBuilder sb = new StringBuilder() ;
        
       if(n% 2 == 0)
       {
         sb.append(n+2*k) ;  
       }
       
       else{
           
           if( k == 1)
           {
               sb.append(help(n) + n ) ;
           }
           
           else{
               
               long ans = help(n) + n ;
               sb.append(ans + 2*(k-1) ) ;
               
           }
           
       }
       
       
       out.println(sb) ;
      }  
       
        out.flush() ;
       
    }
}