#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const long long INF = 1e18;
const int Mod = 1e9 + 7;
const int maxn = 1e6 + 10;
bool isprime[maxn];
int f[maxn];
void Prime() {
  int i, j, s = 0;
  memset(isprime, true, sizeof(isprime));
  memset(f, 0, sizeof(f));
  int m = sqrt(maxn + 0.5);
  for (i = 2; i <= m; i++) {
    if (isprime[i]) {
      f[i] = i;
      for (j = i * i; j <= maxn; j += i) {
        isprime[j] = 0;
        if (!f[j]) f[j] = i;
      }
    }
  }
}
int solve(int n, int k) {
  if (k == 0) return n;
  return solve(n + f[n], k - 1);
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t, n, k;
  cin >> t;
  while (t--) {
    cin >> n >> k;
    for (int i = 2; i <= n; i++) {
      if (n % i == 0) {
        n += i;
        k--;
        break;
      }
    }
    long long ans = n;
    cout << ans + 2 * k << endl;
  }
  return 0;
}
