CF1471B.Strange List

You have given an array $a$ of length $n$ and an integer $x$ to a brand new robot. What the robot does is the following: it iterates over the elements of the array, let the current element be $q$. If $q$ is divisible by $x$, the robot adds $x$ copies of the integer $\frac{q}{x}$ to the end of the array, and moves on to the next element. Note that the newly added elements could be processed by the robot later. Otherwise, if $q$ is not divisible by $x$, the robot shuts down.

Please determine the sum of all values of the array at the end of the process.

你给一个长度为 $n$ 的数组 $a$ 和一个整数 $x$，交由一个全新的机器人处理。机器人的操作如下：它遍历数组中的元素，设当前元素为 $q$。若 $q$ 能被 $x$ 整除，则机器人将 $x$ 个整数 $\frac{q}{x}$ 添加到数组末尾，并继续处理下一个元素。注意，新添加的元素后续也可能被机器人处理；否则，若 $q$ 不能被 $x$ 整除，机器人立即关机。

请计算该过程结束后数组中所有元素的总和。

The first input line contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases.

The first line of each test case contains two integers $n$ and $x$ ($1 \leq n \leq 10^5$, $2 \leq x \leq 10^9$) — the length of the array and the value which is used by the robot.

The next line contains integers $a_1$, $a_2$, ..., $a_n$ ($1 \leq a_i \leq 10^9$) — the initial values in the array.

It is guaranteed that the sum of values $n$ over all test cases does not exceed $10^5$.

第一行输入包含一个整数 $t$（$1 \leq t \leq 100$）—— 表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $x$（$1 \leq n \leq 10^5$，$2 \leq x \leq 10^9$）—— 分别表示数组的长度以及机器人所使用的值。

下一行包含 $n$ 个整数 $a_1$, $a_2$, ..., $a_n$（$1 \leq a_i \leq 10^9$）—— 表示数组的初始值。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

For each test case output one integer — the sum of all elements at the end of the process.

对于每个测试用例，输出一个整数——即该过程结束时所有元素的总和。

In the first test case the array initially consists of a single element $[12]$, and $x=2$. After the robot processes the first element, the array becomes $[12, 6, 6]$. Then the robot processes the second element, and the array becomes $[12, 6, 6, 3, 3]$. After the robot processes the next element, the array becomes $[12, 6, 6, 3, 3, 3, 3]$, and then the robot shuts down, since it encounters an element that is not divisible by $x = 2$. The sum of the elements in the resulting array is equal to $36$.

In the second test case the array initially contains integers $[4, 6, 8, 2]$, and $x=2$. The resulting array in this case looks like $ [4, 6, 8, 2, 2, 2, 3, 3, 4, 4, 1, 1, 1, 1, 1, 1]$.

在第一个测试用例中，数组初始仅包含一个元素 $[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]$。