题目描述

你有一个长度为 $n$ 的数组 $a$ 和一个整数 $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$），分别表示数组的长度和机器人的参数 $x$。

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

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

输出格式

对于每个测试用例，输出一个整数，表示最终数组中所有元素的和。

说明/提示

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

由 ChatGPT 4.1 翻译

样例

2
1 2
12
4 2
4 6 8 2

36
44