#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long INFLL = 1e18;
const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;
int t;
long long n, k;
int main() {
  scanf("%d", &t);
  for (int T = 0; T < t; T++) {
    scanf("%lld %lld", &n, &k);
    long long mn = n;
    for (int i = 2; i < sqrt(n) + 1; i++)
      if (n % i == 0) {
        mn = i;
        break;
      }
    n += mn;
    k--;
    n += 2LL * k;
    printf("%lld\n", n);
  }
  return 0;
}
