#include <bits/stdc++.h>
using namespace std;
int main() {
  vector<long long> v;
  int k;
  cin >> k;
  long long a[k];
  for (int j = 0; j < k; j++) {
    cin >> a[j];
    long long p;
    cin >> p;
    if (a[j] % 2 == 0) {
      v.push_back(a[j] + 2 * p);
    } else {
      int count = 0;
      int y = sqrt(a[j]);
      for (int i = 3; i <= y; i++) {
        if (a[j] % i == 0) {
          v.push_back(a[j] + i + 2 * p - 2);
          count = 1;
          break;
        } else {
        }
      }
      if (count == 0) {
        v.push_back(a[j] * 2 + 2 * p - 2);
      }
    }
  }
  for (int i = 0; i < k; i++) {
    cout << v[i] << endl;
  }
}
