CF1699E Three Days Grace

给定一个初始有 $n$ 个元素的可重复集合 $A$，其中每个元素都在 $1$ 到 $m$ 之间。 每次操作可以将 $A$ 中的一个元素（称之为 $x$）从 $A$ 中删除，然后在 $A$ 中加入两个元素 $p,q$，满足 $p\cdot q=x$ 且 $p,q>1$。 显然每次操作后 $A$ 的大小会增加 $1$。 定义 $A$ 的平衡值为 $A$ 中的最大值减去最小值，求任意次操作（可以是 $0$ 次）后最小可能的平衡值。

第一行输入一个整数 $T$（$1\leq T\leq 10^5$），表示测试数据组数。 每个测试数据包含两行。 对于每个测试数据： 第一行包含两个整数 $n$（$1\leq n\leq 10^6$），$m$（$1\leq m\leq 5\cdot 10^6$），分别表示数组 $A$ 的元素个数以及 $A$ 中元素的最大可能值。 保证所有测试数据中的 $T$ 个 $n$ 之和不超过 $10^6$，所有测试数据中的 $T$ 个 $m$ 之和不超过 $5\cdot 10^6$。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots ,a_n$（$1\leq a_i\leq 5\cdot 10^6$）。

对于每个测试数据，输出一行一个整数，表示最小可能平衡值。

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