C. Целый корень степени k

Для каждого запроса $(n, k)$ найдите $\lfloor \sqrt[k]{n} \rfloor$ — наибольшее целое $r$, для которого $r^k \le n$.

В первой строке $q$ ($1 \le q \le 10^5$). В каждой из следующих $q$ строк — числа $n$ и $k$ ($1 \le n \le 10^{18}$, $1 \le k \le 60$).

Для каждого запроса выведите $\lfloor \sqrt[k]{n} \rfloor$ в отдельной строке.