import java.util.*;
public class Main {
public static void main(String args[]) {
// Your Code Here
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t>0){
long n =sc.nextLong();
int k = sc.nextInt();
if(k==1){
System.out.println(n);
}
else{
long a = 1;
long ans=0;
while(Math.pow(a++, k)<n) {
ans = a;
// System.out.println(a);
}
System.out.println(ans-1);
}
t--;
}
}
}