#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define FAST ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define INF INT_MAX
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define nl "\n"
using namespace std;
const ll MOD  = 1e9+7;
const int mxN = 2e5+1;


int main()
{
    FAST
    //==================
    ll t; cin >> t;
    while(t--){
        ll n , a ; cin >> n>> a;
        bool is = 1;
        ll k = a;
        for(ll i =2 ;i*i<=k;i++){
            if(k%i == 0){
                is =0;
                break;
            }
        }
        if(is)cout << n << nl;
        else{
            ll p = a+1;
            while(p*p <=n){
                p*=p;
            }
            cout << p << nl;
        }


    }



}