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.util.*;
/**
 * Main
 */
public class Main {
       static int mod  = 1000000007;
        static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) {
       MyScanner ms  = new MyScanner();
        // and b  a is a divior of b i fnad onlf thery exist an integer c
        //a*c = b
        //n>2 f(n) the smallest positive diviros of n except of 1
        //n =5, the new values of n will be equla to 10
        //will be given n and k then wil be add to n-k then k

        //the unkonwn : is n the started vlaue and K the number of time to repeat
        // the data : is the n started value and K the number of time to repeat
        //The condition:  is n shte started value and 
        //is the number is even then put two
        //i have to the find the prime number the divisble to to. The  
        //If the number id odd then it will be divible to a pirme number ebfore any other number
        BitSet bs = new BitSet(100001);
        int max = 100000;
        for(long i = 2;i<=max;i++){
            if(bs.get((int)i)){
                for(long j=i*i;j<=max;i++){
                    bs.set((int)j);
                }
            }
            i = bs.nextClearBit((int)i+1);
        }
        //the idea is wil not work I tdidn't think aboyut the restiricion of k
        //if n is even the the number will be increase by two
        //if n is odd plus odd plus odd is even then i ID on have to find the math
        int t = ms.nextInt();
        while(t-->0){
            int n= ms.nextInt();int k = ms.nextInt();
            int sum=n;
           if((n&1)==0){
               pw.println(k*2+n);
           }else{
               int p = f(n, bs);
               n+=p;
               k--;
               pw.println(k*2+n);
           }
        }
    pw.flush();
    }
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;
   
        public MyScanner() {
           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;
        }
  
     }
     public static int f(int n, BitSet bs){
        if(n%2==0)
        return 2;
        int j=3;
        while(n%j!=0){
            j = bs.nextClearBit(j+1);
        }
        return j;
    }
}