#include <iostream>
using namespace std;

// Problem A : Orac and Factors
//思路：对于偶数，每次+2； 对于奇数，找到什么时候变成偶数即可
int main() {
    int t;
    scanf("%d", &t);

    while (t--) {
        int n, k;
        scanf("%d%d", &n, &k);
        int i = 0;
        while (true) {
            if (n % 2 == 0) {
                break;
            }
            for (int j = 3; j <= n; j++) {
                if (n % j == 0) {
                    i++;
                    n += j;
                    break;
                }
            }
        }
        n += 2 * (k - i);
        printf("%d\n", n);
    }

    return 0;
}