CF2267C CF2267C GCD Treasury

贪心的海盗Dimash发现了一处宝藏库。宝藏库一共有 $n$ 堆硬币，编号从 $1$ 到 $n$。第 $i$ 堆恰好有 $a_i$ 枚硬币。海盗Dimash手里有一个数字 $x$，他可以借助这个数字盗取宝藏库中的硬币。盗取过程如下： - 首先，他选择一个下标 $1 \le i \le n$，满足 $a_i > 0$，并且 $\gcd(a_i, x) \neq 1$。如果不存在这样的下标，海盗停止盗取。 - 记 $\gcd(a_i, x) = g$。海盗从第 $i$ 堆偷走恰好 $g$ 枚硬币，之后 $a_i$ 的值减少 $g$。 - 最后，他将 $x$ 更新为 $g$，继续盗取硬币。 你的任务是帮助海盗偷走尽可能多的硬币。求最多可以从宝藏库偷走的硬币总数。 注：$\gcd(a_i, x)$ 代表 $a_i$ 和 $x$ 的最大公约数。

每组数据包含多组测试用例。第一行输入测试用例数量 $t$（$1 \le t \le 10^4$）。接下来是每组测试用例的描述。 每组测试用例第一行包含两个整数 $n$ 和 $x$（$1 \le n, x \le 3 \cdot 10^5$）——宝藏库硬币堆的数量以及海盗初始持有的数字。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 3 \cdot 10^5$）。 保证所有测试用例的 $n$ 之和不超过 $3 \cdot 10^5$。

对于每组测试用例，输出一行一个整数表示能够偷走的硬币最大数量。

在第一组测试用例中，一枚硬币都无法盗取。 第二组测试用例，海盗的盗取步骤如下： - 海盗选择第 $3$ 堆。取走 $4$ 枚硬币，宝藏库变为 $[2, 3, 0]$，$x$ 更新为 $4$。 - 海盗选择第 $1$ 堆。取走 $2$ 枚硬币，宝藏库变为 $[0, 3, 0]$，$x$ 更新为 $2$。 - 没有符合条件的下标，海盗停止。海盗一共盗取 $4 + 2 = 6$ 枚硬币。