CF1699E.Three Days Grace

Ibti was thinking about a good title for this problem that would fit the round theme (numerus ternarium). He immediately thought about the third derivative, but that was pretty lame so he decided to include the best band in the world — Three Days Grace.

You are given a multiset $A$ with initial size $n$, whose elements are integers between $1$ and $m$. In one operation, do the following:

• select a value $x$ from the multiset $A$, then
• select two integers $p$ and $q$ such that $p, q \gt 1$ and $p \cdot q = x$. Insert $p$ and $q$ to $A$, delete $x$ from $A$.

Note that the size of the multiset $A$ increases by $1$ after each operation.

We define the balance of the multiset $A$ as $\max(a_i) - \min(a_i)$. Find the minimum possible balance after performing any number (possible zero) of operations.

伊布提正在为这道题构思一个契合本轮主题（“三进制数”）的优秀标题。他立刻想到了“三阶导数”，但这未免太过平庸，于是他决定加入世界上最棒的乐队——Three Days Grace。

给定一个初始大小为 $n$ 的多重集 $A$，其中所有元素均为介于 $1$ 与 $m$ 之间的整数。每次操作执行如下步骤：

• 从多重集 $A$ 中选取一个值 $x$；
• 再选取两个整数 $p$ 和 $q$，满足 $p, q \gt 1$ 且 $p \cdot q = x$；将 $p$ 和 $q$ 插入 $A$，并从 $A$ 中删除 $x$。

注意：每次操作后，多重集 $A$ 的大小增加 $1$。

我们定义多重集 $A$ 的平衡值为 $\max(a_i) - \min(a_i)$。求在执行任意次数（包括零次）操作后，所能达到的最小可能平衡值。

The first line of the input contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases.

The second line of each test case contains two integers $n$ and $m$ ($1 \le n \le 10^6$, $1 \le m \le 5 \cdot 10^6$) — the initial size of the multiset, and the maximum value of an element.

The third line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le m$) — the elements in the initial multiset.

It is guaranteed that the sum of $n$ across all test cases does not exceed $10^6$ and the sum of $m$ across all test cases does not exceed $5 \cdot 10^6$.

输入的第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。

每个测试用例的第二行包含两个整数 $n$ 和 $m$（$1 \le n \le 10^6$，$1 \le m \le 5 \cdot 10^6$），分别表示多重集的初始大小以及元素的最大值。

每个测试用例的第三行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le m$），表示初始多重集中的元素。

保证所有测试用例中 $n$ 的总和不超过 $10^6$，且所有测试用例中 $m$ 的总和不超过 $5 \cdot 10^6$。

For each test case, print a single integer — the minimum possible balance.

对于每个测试用例，输出一个整数——可能的最小余额。

In the first test case, we can apply the operation on each of the $4$s with $(p,q) = (2,2)$ and make the multiset ${2,2,2,2,2,2,2}$ with balance $\max({2,2,2,2,2,2,2}) - \min({2,2,2,2,2,2,2}) = 0$. It is obvious we cannot make this balance less than $0$.

In the second test case, we can apply an operation on $12$ with $(p,q) = (3,4)$. After this our multiset will be ${3,4,2,3}$. We can make one more operation on $4$ with $(p,q) = (2,2)$, making the multiset ${3,2,2,2,3}$ with balance equal to $1$.

In the third test case, we can apply an operation on $35$ with $(p,q) = (5,7)$. The final multiset is ${6,5,7}$ and has a balance equal to $7-5 = 2$.

In the forth test case, we cannot apply any operation, so the balance is $5 - 1 = 4$.

在第一个测试用例中，我们可以对每个 $4$ 应用操作 $(p,q) = (2,2)$，从而得到多重集 ${2,2,2,2,2,2,2}$，其平衡值为 $\max({2,2,2,2,2,2,2}) - \min({2,2,2,2,2,2,2}) = 0$。显然，我们无法使该平衡值小于 $0$。

在第二个测试用例中，我们可以对 $12$ 应用操作 $(p,q) = (3,4)$。操作后，我们的多重集变为 ${3,4,2,3}$。接着，我们可再对 $4$ 应用一次操作 $(p,q) = (2,2)$，使得多重集变为 ${3,2,2,2,3}$，其平衡值为 $1$。

在第三个测试用例中，我们可以对 $35$ 应用操作 $(p,q) = (5,7)$。最终的多重集为 ${6,5,7}$，其平衡值为 $7-5 = 2$。

在第四个测试用例中，我们无法执行任何操作，因此平衡值为 $5 - 1 = 4$。