Strange List

题意翻译

### 题目描述 您将一个长度为 $n$ 的数组 $a$ 和一个整数 $x$ 给了机器人。机器人的操作将会遵循以下原则：对于数组的元素进行迭代，当前的元素为 $q$。如果 $q$ 被 $x$ 整除，那么机器人会将 $x$ 个整数 $\frac{q}{x}$ 添加到数组的末尾，然后移到下一个元素。否则，机器人停止工作。 请在机器人停止工作时确定数组所有值的总和。 ### 输入格式 第一行包含一个整数 $t(1\le t\le100)$ 输入数据的组数。 接下来对于每组数据包含一个整数 $n,x(1\le n\le 100000,1\le x\le 10^9)$数组的长度和机器人的工作值。 接下来的一行包含 $n$ 个整数， $a_1,a_2,\cdots ,a_n$ 表示 $a$ 数组。 确保所有测试用例的值 $n$ 的总和不超过 $10 ^ 5$。

题目描述

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.

输入输出格式

输入格式

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 $ .

输出格式

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

输入输出样例

输入样例 #1

2
1 2
12
4 2
4 6 8 2

输出样例 #1

36
44

说明

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] $ .