Если вас интересует математика, то эта задача для вас.
Будем называть целое число $$$n$$$ $$$k$$$-степенным, если его можно разложить в сумму различных степеней числа $$$k$$$, то есть если $$$n$$$ представимо в виде $$$n = k^{a_1} + k^{a_2} + \ldots + k^{a_d}$$$, где все $$$a_i$$$ целые и $$$a_i \ne a_j$$$ для всех $$$i \ne j$$$.
Ответьте на множество запросов: какое минимальное целое число, большее либо равное $$$n_i$$$, является $$$k_i$$$-степенным?
Первая строка ввода содержит целое число $$$q$$$ — количество запросов, на которые вам предстоит ответить ($$$1 \le q \le 10^5$$$).
Каждая из следующих $$$q$$$ строк содержит два целых числа $$$n_i$$$ и $$$k_i$$$, описывающие $$$i$$$-й запрос ($$$1 \le n_i \le 10^9$$$; $$$2 \le k_i \le 10^9$$$).
Выведите $$$q$$$ строк, в $$$i$$$-й из которых выведите минимальное $$$k_i$$$-хорошее число, большее либо равное $$$n_i$$$.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 0 | – | примеры из условия | полная | |
| 1 | 6 | $$$n_i \le 10^5$$$, $$$k_i = 2$$$ для всех $$$i$$$ | первая ошибка | |
| 2 | 9 | $$$n_i \le k_i$$$ для всех $$$i$$$ | первая ошибка | |
| 3 | 10 | $$$q = 1$$$; $$$n_i \le 10^5$$$ для всех $$$i$$$ | полная | |
| 4 | 11 | $$$n_i \le 10^5$$$, $$$k_i = 10$$$ для всех $$$i$$$ | первая ошибка | |
| 5 | 13 | $$$n_i \le 10^5$$$ для всех $$$i$$$; $$$k_i = k_j$$$ для всех $$$i, j$$$ | 1, 4 | первая ошибка |
| 6 | 16 | $$$q \le 500$$$; $$$k_i \ge 20$$$ для всех $$$i$$$ | первая ошибка | |
| 7 | 35 | без дополнительных ограничений | 0 – 7 | первая ошибка |
71 22 36 513 1014 33620 1210000 3
1 3 6 100 27 20736 19683