题目描述

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

输入格式

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

输出格式

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

3
4 2
9 2
64 3

2
3
4