Степенные числа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Если вас интересует математика, то эта задача для вас.

Будем называть целое число $$$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примеры из условияполная
16$$$n_i \le 10^5$$$, $$$k_i = 2$$$ для всех $$$i$$$первая ошибка
29$$$n_i \le k_i$$$ для всех $$$i$$$первая ошибка
310$$$q = 1$$$; $$$n_i \le 10^5$$$ для всех $$$i$$$полная
411$$$n_i \le 10^5$$$, $$$k_i = 10$$$ для всех $$$i$$$первая ошибка
513 $$$n_i \le 10^5$$$ для всех $$$i$$$; $$$k_i = k_j$$$ для всех $$$i, j$$$ 1, 4первая ошибка
616$$$q \le 500$$$; $$$k_i \ge 20$$$ для всех $$$i$$$первая ошибка
735без дополнительных ограничений0 – 7первая ошибка

Пример

Входные данные
7
1 2
2 3
6 5
13 10
14 3
3620 12
10000 3
Выходные данные
1
3
6
100
27
20736
19683