#include <bits/stdc++.h>
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int a, b;
    scanf("%d%d", &a, &b);
    if (a % 2 == 0) {
      printf("%d\n", a + 2 * b);
    } else {
      int max;
      for (int i = 1; i <= a; i++) {
        if (a % i == 0 && i != 1) {
          max = i;
          break;
        }
      }
      printf("%d\n", a + max + 2 * (b - 1));
    }
  }
}
