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.* ;
import java.lang.* ;
public class codeforceA {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		 Scanner in =  new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int[] arr= new int[]{  2     , 3   ,    5 ,      7 ,     11 ,     13  ,    17   ,   19 ,     23 ,

            29  ,    31 ,     37  ,    41 ,     43   ,   47  ,    53  ,    59 ,     61,

            67  ,    71   ,   73  ,    79  ,   83    ,  89  ,    97  ,   101 ,    103 ,

           107  ,   109  ,   113   ,  127 ,    131  ,   137 ,    139  ,   149  ,   151 ,

           157  ,   163  ,   167 ,    173  ,   179   ,  181 ,    191  ,   193  ,   197 ,

           199   ,  211  ,   223  ,   227    , 229    , 233  ,   239  ,   241  ,   251 ,

           257  ,   263   ,  269   ,  271   ,  277  ,   281 ,    283  ,   293  ,   307 ,

           311 ,    313 ,    317 ,    331  ,   337  ,   347  ,   349 ,    353   ,  359 ,

           367 ,    373   ,  379 ,    383  ,   389 ,    397  ,   401  ,   409 ,    419 ,

           421 ,    431 ,    433 ,    439   ,  443  ,   449 ,    457 ,    461 ,    463 ,

           467  ,   479 ,    487   ,  491  ,   499  ,   503   ,  509  ,   521  ,   523 ,

           541,     547 ,    557   ,  563  ,   569 ,    571  ,   577,     587  ,   593 ,

           599 ,    601 ,    607 ,    613  ,   617,     619,     631,     641 ,    643 ,

           647 ,    653  ,   659 ,    661 ,    673 ,    677,     683,     691,     701 ,

           709,     719 ,    727 ,    733,     739 ,    743  ,   751,     757,     761, 

           769,     773,     787 ,    797 ,    809,     811 ,    821,     823  ,   827 ,

           829  ,   839 ,    853 ,    857  ,   859   ,  863   ,  877 ,    881 ,    883, 

           887 ,    907  ,   911 ,    919   ,  929  ,   937 ,    941 ,    947 ,    953 ,

           967  ,   971 ,    977,     983 ,    991 ,    997, 1009};
         int t= in.nextInt();
        // System.out.println(t);
         for( int i=1;i<=t;i++){
            long n=in.nextInt();
            long k=in.nextInt();
            
           
            	long fn=n;
            //	System.out.println(n);
            	for( int l=0;l<arr.length;l++) {
            	//	System.out.println(arr[l] +" is l");
            	//	System.out.println(l +" is lu");
            		if(n%arr[l]==0) {
            			fn=arr[l];
            			//n+=arr[l];
            			//System.out.println("fn is" +fn);
            			//n=fn+n;
            			break;
            			
            		}
            		if(arr[l]>(int)Math.sqrt(n)) {
            			break;
            		}
            	
            	
            	//System.out.println("fn is1 " +fn);
              }
            	n+=fn;
              n=(k-1)*2+n;
            System.out.println(n   );
            }
         }
	}


