#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
const long long mod = 998244353;
const long long INF = (4e18);
int prime[((10000) + 5)], pn;
bool jud[((10000) + 5)];
void init() {
  pn = 0;
  for (int i = 2; i <= (10000); i++) {
    if (!jud[i]) prime[++pn] = i;
    for (int j = 1; j <= pn; j++) {
      int cnt = prime[j] * i;
      if (cnt > (10000)) break;
      jud[cnt] = true;
      if (i % prime[j] == 0) break;
    }
  }
}
int main() {
  init();
  int t;
  scanf("%d", &t);
  while (t--) {
    long long n, k;
    scanf("%lld%lld", &n, &k);
    long long f = 0;
    for (int i = 1; i <= pn; i++) {
      if (n % prime[i] == 0) {
        f = prime[i];
        break;
      }
    }
    if (!f) f = n;
    long long ans;
    if (n / f == 1) {
      ans = n + f + 2 * (k - 1);
    } else {
      long long r = n / f;
      if (r % 2 == 1) {
        ans = n + f + 2 * (k - 1);
      } else {
        ans = n + f * k;
      }
    }
    printf("%lld\n", ans);
  }
  return 0;
}
