#include <bits/stdc++.h>
using namespace std;
int getDiv(int n) {
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) return i;
  }
  return n;
}
int main() {
  int cs;
  scanf("%d", &cs);
  while (cs--) {
    int n, k;
    scanf("%d %d", &n, &k);
    int d = getDiv(n);
    printf("%d\n", n + d + (k - 1) * 2);
  }
  return 0;
}
