Description

给定正整数B和N，找出一个整数A，使得A^N最靠近B。（A是逼近B的第N个根）
注意A^N可能小于、等于或者大于B。

Input

第一行输入T，表示有T组测试数据。每组测试数据输入一行，每一行输入正整数B和N，（0< B ≤1000000）,(10>N>0)。

Output

每组数据输出一行，输出上文定义的A。

Sample Input

2
4 3
1000000 5

Sample Output

1
16

HINT

Source