#include <bits/stdc++.h>
using namespace std;
bool sbs = false;
bool break1;
string str, str1, zxc, final1, final2;
long long t, iman, len;
long long first;
long long last;
long long n1, n2, n3;
long long m1, m2, m3, n, m;
long long all = 0, l, l1, l2;
long double x;
long long z, z1, xx;
void fex(unsigned long long x, unsigned long long y) {
  all = x;
  z = 0;
  if (x % 2 == 0) {
    all += (2 * y);
  } else if (x % 3 == 0) {
    all += 3;
    all += (2 * (y - 1));
  } else if (x % 5 == 0) {
    all += 5;
    all += (2 * (y - 1));
  } else if (x % 7 == 0) {
    all += 7;
    all += (2 * (y - 1));
  } else {
    all *= 2;
    all += (2 * (y - 1));
  }
  cout << all << endl;
}
int main() {
  cin >> n;
  while (n--) {
    z = 2;
    cin >> n1 >> n2;
    all = n1;
    if (n1 % 2 == 0) {
      z = 2;
    } else {
      for (long long int i = 3; i * i <= n1; i += 2) {
        if (n1 % i == 0) {
          z = i;
          break;
        }
      }
    }
    if (z == 0 || n1 % z != 0) z = n1;
    all += z;
    all += (2 * (n2 - 1));
    cout << all << endl;
  }
  return 0;
}
