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.
//package com.example.programming;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.sql.Time;
import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Date;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.Timer;
import java.util.TreeSet;
import java.util.Vector;


public class CodeforcesProblems {

    static String[] sTakeInputs;
    static int sInputPos = 0;
    static BufferedReader sBufferedReader;
    static StringBuilder sOutputBuilder;

    static int[] scanIntArray() throws Exception{
        String[] inputs = sBufferedReader.readLine().trim().split(" ");
        int[] arr = new int[inputs.length];
        for(int i = 0; i<inputs.length; i++) arr[i] = Integer.parseInt(inputs[i]);
        return arr;
    }

    static long[] scanLongArray() throws Exception{
        String[] inputs = sBufferedReader.readLine().trim().split(" ");
        long[] arr = new long[inputs.length];
        for(int i = 0; i<inputs.length; i++) arr[i] = Long.parseLong(inputs[i]);
        return arr;
    }

    static int scanInt() throws Exception{
        return Integer.parseInt(sBufferedReader.readLine().trim());
    }

    static long scanLong() throws Exception{
        return Long.parseLong(sBufferedReader.readLine().trim());
    }

    static int nextInt() throws Exception {
        if(sInputPos == 0) sTakeInputs = sBufferedReader.readLine().trim().split(" ");
        if(sTakeInputs.length <= sInputPos) {
            sTakeInputs = sBufferedReader.readLine().trim().split(" ");
            sInputPos = 0;
        }
        return Integer.parseInt(sTakeInputs[sInputPos++]);
    }

    static long nextLong() throws Exception {
        if(sInputPos == 0) sTakeInputs = sBufferedReader.readLine().trim().split(" ");
        if(sTakeInputs.length <= sInputPos) {
            sTakeInputs = sBufferedReader.readLine().trim().split(" ");
            sInputPos = 0;
        }
        return Long.parseLong(sTakeInputs[sInputPos++]);
    }

    static String nextString() throws Exception {
        if(sInputPos == 0) sTakeInputs = sBufferedReader.readLine().trim().split(" ");
        if(sTakeInputs.length <= sInputPos) {
            sTakeInputs = sBufferedReader.readLine().trim().split(" ");
            sInputPos = 0;
        }
        return sTakeInputs[sInputPos++];
    }

    static void print(int val, char ch) {
        sOutputBuilder.append(val).append(ch);
    }

    static void print(long val, char ch) {
        sOutputBuilder.append(val).append(ch);
    }

    static void print(float val, char ch) {
        sOutputBuilder.append(val).append(ch);
    }

    static void print(double val, char ch) {
        sOutputBuilder.append(val).append(ch);
    }

    static void print(String val, char ch) {
        sOutputBuilder.append(val).append(ch);
    }
    static void print(StringBuilder val, char ch) {
        sOutputBuilder.append(val).append(ch);
    }

    static void print(int x) {
        sOutputBuilder.append(x);
    }

    static void print(char ch) {
        sOutputBuilder.append(ch);
    }

    static void printf() {
        System.out.print(sOutputBuilder);
        sOutputBuilder = new StringBuilder();
    }

    static void solve(boolean[] track, ArrayList<Integer> primes) throws Exception{
        int n = nextInt();
        long k = nextInt();
        long ans = n;
        if(!track[n]) {
            ans = ans + ans + 2L*(k-1);
            print(ans,'\n'); return;
        }
        for(int p : primes) {
            if(n%p == 0) {
                ans += (long) p;
                ans += 2L*(k-1);
                print(ans,'\n'); return;
            }
        }
    }




    public static void main (String[] args) throws Exception {
        sBufferedReader = new BufferedReader(new InputStreamReader(System.in));
        sOutputBuilder = new StringBuilder();
        boolean[] track = new boolean[1000001];
        int lim = track.length-1;
        for(int i = 2; i<=track.length/2; i++) {
            if(!track[i]) {
                for(int j = 2; i*j<=lim; j++) track[i*j] = true;
            }
        }
        ArrayList<Integer> primes = new ArrayList<>();
        for(int i = 2; i<lim; i++) {
            if(!track[i]) {
                primes.add(i);
            }
        }
        int t = nextInt();
        while(t>0) {solve(track, primes); t--;}
        printf();
    }

}
