题目描述

一个简单的问题，给定 \(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\)。

样例输入

3
4 2
9 2
64 3

样例输出

2
3
4