include<bits/stdc++.h>

using namespace std;

define min(a,b) ((a)<(b)?(a):(b))

define max(a,b) ((a)>(b)?(a):(b))

define lli long long int

define ll long long

int main() { lli n,k,c,t.i; cin>>t; while(t--) { cin>>n>>k; c=n; for(i=2; i<=10; i++) { if(n%i==0) { c=i; break; } }

n+=c;
cout<<n+(k-1)*2<<"\n";

} return 0; }