#include <bits/stdc++.h>
using namespace std;
vector<int> queries;
int smalldiv(int prob) {
  for (int i = 2; i * i <= prob; i++) {
    if (prob % i == 0) return i;
  }
  return prob;
}
int solve() {
  int N, K;
  cin >> N >> K;
  int outp = N;
  return N + smalldiv(N) + 2 * K - 2;
  return outp;
}
int main() {
  int T;
  cin >> T;
  for (int i = 0; i < T; i++) cout << solve() << '\n';
}
