#include <bits/stdc++.h>
using namespace std;
int n, k;
void slove() {
  cin >> n >> k;
  int ans = n;
  while (k) {
    if (ans % 2 == 0) {
      ans = ans + 2 * k;
      break;
    }
    bool flag = 1;
    for (int i = 2; i * i <= ans; i++) {
      if (ans % i == 0) {
        ans += i;
        flag = 0;
        break;
      }
    }
    if (flag) ans += ans;
    k--;
  }
  cout << ans << endl;
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    slove();
  }
  return 0;
}
