Если вас интересует математика, то эта задача для вас.
Будем называть целое число \(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
|
7
1 2
2 3
6 5
13 10
14 3
3620 12
10000 3
|
1
3
6
100
27
20736
19683
|