Задача . Степенные числа

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

Будем называть целое число $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$.

1
3
6
100
27
20736
19683