#include <bits/stdc++.h>
long long int lcd(long long int number) {
  for (int i = 2; i <= std::sqrt(number); ++i) {
    if (!(number % i)) {
      return i;
    }
  }
  return number;
}
int main() {
  int tests = 0;
  std::cin >> tests;
  while (tests--) {
    long long int count = 0;
    long long int number = 0;
    std::cin >> number >> count;
    while (count) {
      if (number % 2) {
        number += lcd(number);
      } else {
        number += 2 * count;
        break;
      }
      --count;
    }
    std::cout << number << std::endl;
  }
  return 0;
}
