#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define debug(x) cerr<<#x<<‘=‘<<x<<endl
#define MAXN 10000001
#define NUM 669999

int prime[NUM];
bool flag[MAXN];
int x,y,n;
int f[MAXN];

int Euler(int n){
    int cntprime=0;
    memset(flag,false,sizeof(flag));
    memset(f,0,sizeof(f));
    for (int i = 2; i <= n; i++)
    {
        if (!flag[i]) {
            f[i]=i; //第一句 
            prime[++cntprime] = i;
        }
          for (int j = 1; j <= cntprime && prime[j]*i <= n; j++)    {
            f[prime[j]*i]=f[i]+prime[j];
             flag[i*prime[j]] = true;// 第二句 
             if (i % prime[j] == 0) break;
         }
    }
}

int work(int x,int y){
    while (y){
        if (x==f[x]) {//分解为素数时不会再变化 
        ans=x;
        break;
        }
        else ans=x=f[x];
        y--;
    }
    return ans;    
}
    
int main (){
    Euler(MAXN);
    cin>>n;
    for (int i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        printf("%d\n",work(x,y));
    }
    return 0;
}