| The 2026 ICPC Belarus Regional Contest |
|---|
| Закончено |
One day, Edgar invented a new fancy method to quickly compute the roots of various degrees for a positive integer: take the sum of its digits, and subtract the degree of that root. Just look how easy the calculations are now: $$$\sqrt[2]{25} = 2 + 5 - 2 = 5$$$, $$$\sqrt[2]{196} = 1 + 9 + 6 - 2 = 14$$$, $$$\sqrt[3]{216} = 2 + 1 + 6 - 3 = 6$$$.
To Edgar's great disappointment, in reality, not only does his method not work, but also in multiple cases the true values of roots are not even integers. However, there are definitely a lot of roots that can be extracted that way.
Consider all pairs of positive integers $$$(x, k)$$$, $$$k \geq 2$$$, such that the correct value of the $$$k$$$-th root of $$$x$$$ can be obtained using Edgar's method, and arrange them in a list in ascending order of $$$x$$$ (in case of equal $$$x$$$ – in ascending order of $$$k$$$). Edgar wonders what the $$$q$$$-th pair in the list is, for various values of $$$q$$$. If for that pair $$$x \geq 10^{300}$$$, it is enough to say that the numbers are too large without finding them.
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$): the number of test cases. Then, $$$t$$$ test cases follow.
The only line of a test case contains a single integer $$$q$$$ ($$$1 \leq q \leq 10^9$$$), which means that you should find the $$$q$$$-th pair $$$(x, k)$$$ in the list.
For each test case, print two required integers $$$x$$$ and $$$k$$$ ($$$1 \leq x \lt 10^{300}$$$, $$$k \geq 2$$$). If $$$x$$$ is not less than $$$10^{300}$$$, print two integers -1 -1 for that test case instead.
512561000000000
4 225 2196 2216 3-1 -1
| Название |
|---|


