Недавно первокурсник Максим узнал о гипотезе Коллатца, однако он плохо слушал лекцию, поэтому считает, что в гипотезе упоминается следующий процесс:
Существует переменная \(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\) в итоге получится.
Выходные данные
Для каждого набора входных данных выведите одно целое число — число, которое получится после применения \(k\) операций.
Примечание
В первом наборе входных данных всего одна операция, которая применяется к \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|