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