B. Гипотеза Коллатца
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно первокурсник Максим узнал о гипотезе Коллатца, однако он плохо слушал лекцию, поэтому считает, что в гипотезе упоминается следующий процесс:

Существует переменная $$$x$$$ и константа $$$y$$$. Далее $$$k$$$ раз происходит следующая операция:

  • увеличить $$$x$$$ на $$$1$$$, затем,
  • пока число $$$x$$$ делится нацело на $$$y$$$, делить его на $$$y$$$.
Обратите внимание, что оба этих действия выполняются последовательно в рамках одной операции.

Например, если число $$$x = 16$$$, $$$y = 3$$$ и $$$k = 2$$$, то после одной операции $$$x$$$ станет равен $$$17$$$, а после еще одной операции $$$x$$$ будет равен $$$2$$$, так как после прибавления единицы $$$x = 18$$$ делится два раза на $$$3$$$.

По данным начальным значениям $$$x$$$, $$$y$$$ и $$$k$$$ Максим хочет узнать, какое число $$$x$$$ в итоге получится.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора данных содержит три целых числа $$$x$$$, $$$y$$$ и $$$k$$$ ($$$1 \le x, k \le 10^{9}$$$, $$$2 \le y \le 10^{9}$$$) — начальная переменная, константа и количество операций.

Выходные данные

Для каждого набора входных данных выведите одно целое число — число, которое получится после применения $$$k$$$ операций.

Пример
Входные данные
13
1 3 1
2 3 1
24 5 5
16 3 2
2 2 1
1337 18 1
1 2 144133
12345678 3 10
998244353 2 998244353
998244353 123456789 998244352
998244354 998241111 998244352
998244355 2 9982443
1000000000 1000000000 1000000000
Выходные данные
2
1
1
2
3
1338
1
16936
1
21180097
6486
1
2
Примечание

В первом наборе входных данных всего одна операция, которая применяется к $$$x = 1$$$, в результате $$$x$$$ становится равен $$$2$$$.

Во втором наборе входных данных к $$$x = 2$$$ в рамках одной операции прибавляется единица и $$$x$$$ делится на $$$y = 3$$$, в результате $$$x$$$ становится равен $$$1$$$.

В третьем наборе данных $$$x$$$ изменяется так:

  • После первой операции $$$x = 1$$$, так как $$$24 + 1 = 25$$$ и $$$25$$$ делится на $$$y = 5$$$ дважды в рамках одной операции.
  • После второй операции $$$x = 2$$$.
  • После третьей операции $$$x = 3$$$.
  • После четвертой операции $$$x = 4$$$.
  • После пятой операции $$$x = 1$$$.