#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::string;
using std::vector;
long long least_divisor(long long n) {
  for (long long k = 2; k * k <= n; ++k) {
    if (n % k == 0) return k;
  }
  return n;
}
void solve() {
  long long n, k;
  cin >> n >> k;
  if (n % 2 == 0) {
    cout << n + k * 2 << '\n';
    return;
  }
  auto d = least_divisor(n);
  cout << n + d + (k - 1) * 2 << '\n';
}
int main() {
  int t;
  cin >> t;
  for (int i = 0; i < t; ++i) solve();
}
