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.
#include <bits/stdc++.h>
long long int mod = 998244353;
using namespace std;
long long int hmaxii = 0;
vector<long long int> values[2 * 100000 + 1];
long long int MAXN = 2 * 100000 + 1;
long long int spf[2 * 100000 + 1];
long long int diff, x, y, z;
long long int flag = 1;
long long int price[1001][1001];
long long int gcd(long long int a, long long int b) {
  return b ? gcd(b, a % b) : a;
}
long long int power(long long int a, long long int b) {
  if (b == 0) {
    return 1;
  }
  long long int temp = power(a, b / 2);
  temp *= temp;
  if (b % 2 == 1) {
    temp *= a;
  }
  return temp;
}
void sieve() {
  spf[1] = 1;
  for (long long int i = 2; i < MAXN; i++) spf[i] = i;
  for (long long int i = 4; i < MAXN; i += 2) spf[i] = 2;
  for (long long int i = 3; i * i < MAXN; i++) {
    if (spf[i] == i) {
      for (long long int j = i * i; j < MAXN; j += i)
        if (spf[j] == j) spf[j] = i;
    }
  }
}
void getFactorization(long long int x,
                      map<long long int, long long int>& counter,
                      set<long long int>& container) {
  vector<long long int> ret;
  while (x != 1) {
    ret.push_back(spf[x]);
    x = x / spf[x];
  }
  for (long long int i = 0; i < ret.size(); i++) {
    long long int index = i;
    while (ret[index] == ret[i] && index < ret.size()) {
      index++;
    }
    counter[ret[i]]++;
    container.insert(ret[i]);
    if (values[ret[i]].size() == 0) {
      values[ret[i]].push_back(index - i);
    } else if (values[ret[i]].size() == 1) {
      long long int a = values[ret[i]][0];
      values[ret[i]][0] = max(a, index - i);
      values[ret[i]].push_back(min(a, index - i));
    } else {
      long long int a = values[ret[i]][0];
      long long int b = values[ret[i]][1];
      if (b >= index - i) {
        values[ret[i]][0] = b;
        values[ret[i]][1] = index - i;
      } else if (a > index - i) {
        values[ret[i]][0] = index - i;
      }
    }
    i = index - 1;
  }
}
long long int number(long long int n) {
  long long int x = 3;
  for (x = 3; x * x <= n; x++) {
    if (n % x == 0) {
      return x;
    }
  }
  return n;
}
void solution() {
  long long int n, k;
  cin >> n >> k;
  long long int ans;
  if (n % 2 == 0) {
    ans = n + k * 2;
  } else {
    ans = n + number(n) + (k - 1) * 2;
  }
  cout << ans << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  sieve();
  long long int t;
  cin >> t;
  while (t--) {
    solution();
  }
  return 0;
}
