你给了一个全新的机器人一个长度为$$$n$$$的数组$$$a$$$和一个整数$$$x$$$。机器人所做的事情如下:它迭代数组的元素,让当前元素为$$$q$$$。如果 $$$q$$$ 可被 $$$x$$$ 整除,则机器人会将整数 $$$\frac{q}{x}$$$ 的 $$$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$$$。
输出
对于每个测试用例,输出一个整数——流程结束时所有元素的总和。
示例
输入 #1
2 1 2 12 4 2 4 6 8 2
输出 #1
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]$$$。