#include <math.h>
#include <stdio.h>
#include <stdlib.h>
int isp(long long x){
    float a,s;
    s=sqrt(x);
    a=s-(long long)(s);
    if(a==0||a>0.5){
    return 1;
    }
    return 0;
}
int nextnr(long long l){
    float s,a;
    s=sqrt(l);
    a=s-(long long)(s);
    if (a==0){
        return (l+s+1);
    }
    return l+1;
}
long long adg( long long x){
    float s;
    long long a;
    a=(long long)(sqrt(x));
    a=a*(a+1)+1;
    return (a-x);

}
int main(){
    FILE *f1,*f2;
    f1=fopen("progresie.in","r");
    f2=fopen("progresie.out","w");
    long long t,n,r,i,j,l,k;
    fscanf(f1,"%lli",&t);
    while (t){
        fscanf(f1,"%lli %lli",&n,&r);
        i=1;
        while (i>0){
                if (isp(i)==0){
                    k=(long long)(sqrt(i));
                    i=k*(k+1)+1;
                    continue;
                }
                l=i+r;
                j=1;
                while(isp(l)){
                    l=l+r;
                    j=j+1;
                    if (j==n){
                    break;
                    }
                }
                if(j==n){
                    fprintf(f2,"%lli\n",i);
                    break;
                }
                else {
                    k=adg(l);
                    //printf("l %lli k %lli i %lli-->",l,k,i);
                    i=i+k;
                    //printf("k %lli i %lli\n",k,i);
                    continue;
                }
              i=nextnr(i);
        }
        t=t-1;
    }
    fclose(f1);
    fclose(f2);
    return 0;
}