#include <bits/stdc++.h>
using namespace std;
void solve() {
  int m, k;
  cin >> m >> k;
  if (m % 2 == 0) {
    printf("%d\n", m + k * 2);
  } else {
    int t;
    for (int i = 3; i <= m; i += 2) {
      if (m % i == 0) {
        t = i;
        break;
      }
    }
    k--;
    m += t;
    printf("%d\n", m + k * 2);
  }
}
int main() {
  int n;
  cin >> n;
  while (n--) {
    solve();
  }
  return 0;
}
