Si te gustan las matemáticas este ejercicio es para ti, aunque puede que sea más fácil de lo que se pueda esperar de un problema 🙁 así que si no te gustan las matemáticas probablemente puedas resolverlo.

Llamemos un entero ~n~ ~k~-potencia si se puede descomponer en la suma de diferentes potencias de ~k~, en otras palabras, si ~n~ puede ser escrito de la forma ~n = k^{a_1} + k^{a_2} + \dots + k^{a_m}~, donde ~a_i \neq a_j~ para todo ~i \neq j~.

Se le harán varias preguntas: ¿cuál es el número entero más pequeño mayor o igual a ~n_i~ que es ~k_i~-potencia?

Subtareas

• Subtarea 1 (6 puntos): ~n_i \le 10^5~, ~k_i = 2~ para todo ~i~.
• Subtarea 2 (9 puntos): ~n_i \le k_i~ para todo ~i~.
• Subtarea 3 (10 puntos): ~q = 1~, ~n \le 10^5~ para todo ~i~.
• Subtarea 4 (11 puntos): ~n_i \le 10^5~, ~k_i = 10~ para todo ~i~.
• Subtarea 5 (13 puntos): ~n_i \le 10^5~ para todo ~i~, ~k_i = k_j~ para todo ~i, j~.
• Subtarea 6 (16 puntos): ~q \le 500~, ~k_i \ge 20~ para todo ~i~.
• Subtarea 7 (35 puntos): ~1 \le q \le 10^5~, ~n_i \le 10^9~, ~2 \le k_i \le 10^9~.

Entrada

La primera línea contiene un entero ~q~: el número de preguntas que se deben responder.

Le siguen ~q~ líneas contienen dos enteros cada una ~n_i~ y ~k_i~ describiendo cada pregunta.

Salida

Imprima ~q~ líneas con un entero cada una: el entero más pequeño mayor o igual a ~n_i~ que es ~k_i~-potencia.

Ejemplos

Entrada 1

7
1 2
2 3
6 5
13 10
14 3
3620 12
10000 3

Salida 1

1
3
6
100
27
20736
19683