CF2267C.GCD Treasury

The greedy pirate Dimash found a treasury. It consists of $n$ piles of coins, numbered from $1$ to $n$. The $i$-th pile contains exactly $a_i$ coins. Pirate Dimash has a number $x$ that he can use to steal coins from the treasury. The stealing process works as follows:

• First, he chooses an index $1\le i\le n$ such that $a_i\gt 0$ and $\gcd$^{\text{∗}}$(a_i, x) \neq 1$. If there is no such index, the pirate stops.
• Now let $\gcd(a_i, x)$ be $g$. The pirate steals exactly $g$ coins from pile $i$, after which $a_i$ decreases by $g$.
• Finally, he sets $x$ to $g$ and continues stealing coins.

Your task is to help the pirate steal the maximum possible number of coins. Find the maximum number of coins that can be stolen from the treasury.

$^{\text{∗}}$\gcd(a_i, x)$ denotes the greatest common divisor (GCD) of integers $a\_i$ and $x$.

贪婪的海盗迪马什发现了一座宝库。宝库由 $n$ 堆金币组成，编号从 $1$ 到 $n$。第 $i$ 堆恰好包含 $a_i$ 枚金币。海盗迪马什拥有一个数 $x$，他可利用该数从宝库中窃取金币。窃取过程如下：

• 首先，他选择一个下标 $1\le i\le n$，满足 $a_i > 0$ 且 $\gcd$^{\text{∗}}$(a_i, x) \neq 1$。若不存在这样的下标，则海盗停止行动。
• 设此时 $\gcd(a_i, x) = g$。海盗从第 $i$ 堆中恰好窃取 $g$ 枚金币，此后 $a_i$ 减少 $g$。
• 最后，他将 $x$ 更新为 $g$，并继续窃取金币。

你的任务是帮助海盗窃取尽可能多的金币。请找出能从宝库中窃取的金币最大总数。

$^{\text{∗}}$\gcd(a_i, x)$ 表示整数 $a\_i$ 与 $x$ 的最大公约数（GCD）。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $x$ ($1\le n, x\le 3\cdot 10^5$) — the number of piles of coins in the treasury and the pirate's number.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots a_n$ ($1 \le a_i \le 3\cdot 10^5$).

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $x$（$1\le n, x\le 3\cdot 10^5$）—— 分别表示国库中金币堆的数量以及海盗的编号。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots a_n$（$1 \le a_i \le 3\cdot 10^5$）。

保证所有测试用例的 $n$ 之和不超过 $3\cdot 10^5$。

For each test case, output one number — the maximum number of coins that can be stolen.

对于每个测试用例，输出一个数字——能够窃取的硬币的最大数量。

In the first test case, no coin can be stolen.

In the second test case, the pirate steals as follows.

• The pirate chooses pile number $3$. He takes $4$ coins, after which the treasury becomes $[2, 3, 0]$ and $x$ becomes $4$.
• The pirate chooses pile number $1$. He takes $2$ coins, after which the treasury becomes $[0, 3, 0]$, and $x$ becomes $2$.
• No suitable indices remain, so the pirate stops. The pirate managed to take $4 + 2 = 6$ coins.

在第一个测试用例中，无法窃取任何硬币。

在第二个测试用例中，海盗按如下方式窃取硬币：

• 海盗选择第 $3$ 堆。他取走 $4$ 枚硬币，之后金库变为 $[2, 3, 0]$，且 $x$ 变为 $4$。
• 海盗选择第 $1$ 堆。他取走 $2$ 枚硬币，之后金库变为 $[0, 3, 0]$，且 $x$ 变为 $2$。
• 此时已无合适的下标可选，因此海盗停止行动。海盗共窃得 $4 + 2 = 6$ 枚硬币。