#include<iostream>
using namespace std;

long long binpow(long long a, long long b) {
    if (b == 0)
        return 1;
    long long res = binpow(a, b / 2);
    if (b % 2)
        return res * res * a;
    else
        return res * res;
}

int main() {
    long long n, k, t;
    cin>>t;
    while(t--){
        cin>>n>>k;
        long long s = 0;
        long long e = n;
        long long ans = 0;
        long long mid = 0;

        while(s <= e){
        long long mid = (s + e)/2;
            if(binpow(mid, k) <= n){
                ans = mid;
                s = mid + 1;

            }
            else{
                e = mid - 1;
            }
            //cout<<mid<<endl;
        }
    cout<<ans<<endl;
    }

    return 0;
}