题目描述

贪心的海盗迪马什发现了一座金库。金库一共有 $n$ 堆硬币，编号 $1$ 到 $n$。第 $i$ 堆恰好有 $a_i$ 枚硬币。海盗迪马什手里有一个数字 $x$，他可以利用这个数字从金库偷硬币。偷窃过程如下：

• 首先，他选择一个下标 $1\le i\le n$，满足 $a_i>0$ 且 $\gcd(a_i,x)\neq 1$。如果不存在这样的下标，海盗停止偷窃。
• 记 $g=\gcd(a_i,x)$。海盗从第 $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$。

输出格式

对于每组测试数据，输出一个整数：能够偷走的硬币最大数量。

5
3 1
2 3 5
3 4
2 3 4
4 2
2 2 2 2
6 6
2 3 2 3 2 3
7 6
9 9 4 4 4 4 4

0
6
8
9
20

说明

第一组测试数据，一枚硬币都无法偷走。

第二组测试数据，海盗偷窃过程如下：

• 海盗选择第 $3$ 堆。拿走 $4$ 枚硬币，金库变为 $[2,3,0]$，$x$ 更新为 $4$。
• 海盗选择第 $1$ 堆。拿走 $2$ 枚硬币，金库变为 $[0,3,0]$，$x$ 更新为 $2$。
• 没有符合条件的下标，海盗停止。总共偷走 $4 + 2 = 6$ 枚硬币。

原题链接

原题链接