#include <bits/stdc++.h>
using namespace std;
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t, a, b, c, x, y, k, i, j, ans, val, tot, res, pos, n;
  string s;
  cin >> t;
  while (t--) {
    cin >> n >> k;
    res = 0;
    for (i = 2; i <= sqrt(n); ++i) {
      if ((n % i) == 0) {
        val = n + i;
        --k;
        val += 2 * k;
        cout << val << "\n";
        res = 1;
        break;
      }
    }
    if (res == 0) {
      val = 2 * n;
      --k;
      val += 2 * k;
      cout << val << "\n";
    }
  }
  return 0;
}
