#include <bits/stdc++.h>
using namespace std;
unsigned long long int p[1000005];
int32_t main() {
  p[1] = 1;
  unsigned long long int i, j;
  for (i = 2; i <= 1e6; i++)
    if (p[i] == 0)
      for (j = i; j <= 1e6; j += i)
        if (p[j] == 0) p[j] = i;
  unsigned long long int t, n, k;
  cin >> t;
  while (t--) {
    cin >> n >> k;
    unsigned long long int ans = 0;
    if (n % 2 == 1) {
      ans = n + p[n] + 2 * (k - 1);
    } else
      ans = n + 2 * (k);
    cout << ans << "\n";
  }
}
