#include <bits/stdc++.h>
using namespace std;
int t;
long long n;
long long k;
int sd;
int main() {
  cin >> t;
  while (t--) {
    cin >> n >> k;
    sd = 2;
    while (n % sd != 0) {
      sd += 1;
    }
    cout << n + sd + 2 * (k - 1) << endl;
  }
}
