Недавно первокурсник Максим узнал о гипотезе Коллатца, однако он плохо слушал лекцию, поэтому считает, что в гипотезе упоминается следующий процесс:
Существует переменная $$$x$$$ и константа $$$y$$$. Далее $$$k$$$ раз происходит следующая операция:
Например, если число $$$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$$$ операций.
131 3 12 3 124 5 516 3 22 2 11337 18 11 2 14413312345678 3 10998244353 2 998244353998244353 123456789 998244352998244354 998241111 998244352998244355 2 99824431000000000 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$$$ изменяется так:
Название |
---|