题目描述

一个简单的问题，给定 $N,K$，求 $\lfloor \sqrt[k]{N} \rfloor$。大户爱曾经用 C++ 自带的函数求解，代码为 floor(pow(N,1.0/K))，但这样写会造成精度丢失，事实上有一定概率不能求得正确答案，于是大户爱请求你来解决这个问题。题目保证 $2 \le K\le N\le 10^9$。

输入格式

第一行一个整数 T，表示数据组数，保证 $1\le T\le 100$. 第二行开始每行两个整数 $N,K$，表示一个问题。

输出格式

对于每个问题，输出一个整数，表示 $\lfloor \sqrt[k]{N} \rfloor$

输入输出样例 #1

输入 #1

3
4 2
9 2
64 3

输出 #1

2
3
4