#include <bits/stdc++.h>
using namespace std;

const long long infinity = 1e18 + 7;
int T;

bool czy_za_duza(long long liczba, long long n, int m)
{
    long long aktualny = 1;
    for (int i = 1; i <= m; i++)
    {
        if (infinity / liczba >= aktualny) // aktualny * liczba <= infinity
            aktualny *= liczba;
        else
            return true;
        
        if (aktualny > n)
            return true;
    }
    return false;
}

long long bin_search(long long n, int m)
{
    long long p = 1, k = n + 1, s;

    while (k - p > 1)
    {
        s = (p + k) / 2;

        if (czy_za_duza(s, n, m))
            k = s;
        else
            p = s;
    }

    return p;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> T;

    for (int t = 0; t < T; t++)
    {
        long long n;
        int m;
        cin >> n >> m;

        cout << bin_search(n, m) << "\n";        
    }
    return 0;
}