#include <bits/stdc++.h>
using namespace std;
int f[1001001];
int main() {
  for (int i = 2; i * i < 1001001; i++) {
    if (f[i]) continue;
    f[i] = i;
    for (int j = i * i; j < 1001001; j += i)
      if (!f[j]) f[j] = i;
  }
  int T;
  for (scanf("%d", &T); T--;) {
    int n, k;
    scanf("%d%d", &n, &k);
    printf("%d\n", n + (f[n] > 0 ? f[n] : n) + 2 * (k - 1));
  }
  return 0;
}
