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

На Новый Год Дима получил целых два подарка: массив $$$a$$$ длины $$$n$$$ и число $$$x$$$. Оба подарка ему очень понравились, и он сразу же начал экспериментировать с ними. Для этого он отдал их своему новому роботу.

Робот обрабатывает элементы массива по очереди. Пусть текущий рассматриваемый элемент равен $$$q$$$. Если $$$q$$$ кратно $$$x$$$, то робот дописывает в конец массива $$$x$$$ копий числа $$$\frac{q}{x}$$$, а после этого переходит к следующему элементу массива. Обратите внимание, что добавленные элементы могут быть рассмотрены роботом в будущем. Если же $$$q$$$ не делится на $$$x$$$, то робот немедленно прекращает работу.

Определите, чему будет равна сумма элементов массива после того, как робот закончит работу.

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

Первая строка содержит одно число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$x$$$ ($$$1 \leq n \leq 10^5$$$, $$$2 \leq x \leq 10^9$$$) — количество элементов массива и число, на которое робот делит элементы массива.

Следующая строка содержит целые числа $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — изначальные элементы массива.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

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

Пример
Входные данные
2
1 2
12
4 2
4 6 8 2
Выходные данные
36
44
Примечание

В первом наборе входных данных массив изначально состоит лишь из одного числа: $$$[12]$$$, а $$$x = 2$$$. После рассмотрения первого элемента массив превратится в $$$[12, 6, 6]$$$. После обработки второго элемента массив будет содержать элементы $$$[12, 6, 6, 3, 3]$$$. После обработки третьего элемента массив будет состоять из чисел $$$[12, 6, 6, 3, 3, 3, 3]$$$, а после этого робот рассмотрим следующий элемент, который не делится на $$$x=2$$$, и завершит работу. Сумма чисел в итоговом массиве равна $$$36$$$.

Во втором наборе входных данных массив изначально состоит из чисел $$$[4, 6, 8, 2]$$$, а $$$x=2$$$. Итоговый массив выглядит как $$$ [4, 6, 8, 2, 2, 2, 3, 3, 4, 4, 1, 1, 1, 1, 1, 1]$$$.