#include<bits/stdc++.h>

/// abx cautare binara baza
using namespace std;

bool checkOverflow(long long putere, int i){
    return(putere * i > 0) && (putere*i < LONG_MAX);
}

int main(){
    //ifstream fin("date.in.txt");
    ifstream fin("abx.in");
    ofstream fout("abx.out");
    int t;
    long long m;
    fin >> t >> m;

    while(t--){
        long long n;
        fin >> n;

        long long closesCase = 1, lgCase = 99999999999999;

        int i;
        for(i = 2; i*i <= n; ++i){
            int st = 2, dr = 59;

            while(dr - st != 1){
                int mijloc = ( (dr-st) / 2) + st;
                long long putere = 1;

                for(int j = 1; j <= mijloc && checkOverflow(putere, i); ++j)
                    putere *= i;
                //cout << mijloc << " " << putere << "\n";
                if(putere > n)
                    dr = mijloc;
                else
                    st = mijloc;
            }
            //cout <<i << " "<< st << " " << dr << "\n";
            long long nr1 = 1, nr2 = 1;
            while(st--)
                nr1 *= i;
            while(dr--)
                nr2 *= i;
            //cout << nr1 << " " << nr2 << "\n";
            if(lgCase >= abs(n - nr1) && nr1 <= m){
                closesCase = nr1;
                lgCase = abs(n - nr1);
            }
            if(lgCase >= abs(n - nr2) && nr2 <= m){
                closesCase = nr2;
                lgCase = abs(n - nr2);
            }
        }
        long long last = i*i;
        if(lgCase > last - n && last <= m)
            closesCase = last;

        cout << closesCase << "\n";
    }
    return 0;
}