#include<iostream>

#include<cstdio>

#include<cstring>

#include<vector>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

const int Primes[] = {-2,-3,-5,-7,-11,-13,-17,-19,-23,-29,-31,-37,-41,-43,-47,-53,-59,-61,-67,-71};

vector<int> R_number;

void GetR(LL R) {

    R_number.clear();

    for(int i = 0; abs(Primes[i])<= R; ++i) {

        int tmp = Primes[i];

        int Num = R_number.size();

        for(int j = 0; j < Num; ++j) {

            if(abs(R_number[j]*tmp) <= 63)

            R_number.push_back(tmp * R_number[j]);

        }

        R_number.push_back(Primes[i]);

    }

}

LL Cnt(LL N) {

    //GetR(R);

    if(N == 1) return 0;

    LL cnt = N;

    for(int i = 0; i < R_number.size(); ++i) {

        LL tmp = LL (pow(N+0.5, 1.0/abs(R_number[i])) - 1);

        if(R_number[i] < 0) cnt -= tmp;

        else cnt += tmp;

    }

    return cnt - 1;

}

void Solve(LL N,LL R) {

    GetR(R);

    LL ans = N;

    while(1) {

        LL tmp = Cnt(ans);

        if(tmp == N) break;

        ans += N - tmp;

    }

    printf("%lld\n",ans);

}

int main() {

    int t;

    scanf("%d",&t);

    while(t--) {

        LL n,r;

        scanf("%I64d %I64d",&n,&r);

        Solve(n,r);

    }

    return 0;

}