#include<bits/stdc++.h>
using namespace std;
#define int long long int
bool isCorrect(int mid,int n,int k){
	// here we check mid^k<=n or not
	if(pow(mid,k)<=n)return true;
	else return false;
}
int32_t main(){
	int t;cin>>t;
	while(t--){
		int n;cin>>n;
		int k;cin>>k;
		int s=1,e=n;
		int ans;
		while(s<=e){
			int mid=(s+e)/2;
			if(isCorrect(mid,n,k)){
				s=mid+1;
				ans=mid;
			}
			else e=mid-1;
		}
		cout<<ans<<endl;
	}
	return 0;
}

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBpbnQgbG9uZyBsb25nIGludApib29sIGlzQ29ycmVjdChpbnQgbWlkLGludCBuLGludCBrKXsKCS8vIGhlcmUgd2UgY2hlY2sgbWlkXms8PW4gb3Igbm90CglpZihwb3cobWlkLGspPD1uKXJldHVybiB0cnVlOwoJZWxzZSByZXR1cm4gZmFsc2U7Cn0KaW50MzJfdCBtYWluKCl7CglpbnQgdDtjaW4+PnQ7Cgl3aGlsZSh0LS0pewoJCWludCBuO2Npbj4+bjsKCQlpbnQgaztjaW4+Pms7CgkJaW50IHM9MSxlPW47CgkJaW50IGFuczsKCQl3aGlsZShzPD1lKXsKCQkJaW50IG1pZD0ocytlKS8yOwoJCQlpZihpc0NvcnJlY3QobWlkLG4saykpewoJCQkJcz1taWQrMTsKCQkJCWFucz1taWQ7CgkJCX0KCQkJZWxzZSBlPW1pZC0xOwoJCX0KCQljb3V0PDxhbnM8PGVuZGw7Cgl9CglyZXR1cm4gMDsKfQ==

MgoxMDAwMCAxCjEwMDAwMDAwMDAwMDAwMDAgMTA=

2
10000 1
1000000000000000 10