优雅三日

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

有一个包含 $n$ 个整数的可重集合 $A$。你可以进行任意次如下操作：

• 选择集合中的一个数 $x$ 并删除它；
• 选择满足 $p\cdot q=x$ 且 $p,q>1$ 的两个整数 $p,q$，把它们加入集合。

一次操作相当于把一个合数拆成两个大于 $1$ 的因数。定义集合的平衡值为其中最大元素与最小元素之差。请你求经过任意次操作（也可以不操作）后，平衡值的最小可能值。

输入格式

第一行一个整数 $T$，表示测试数据组数。

每组测试数据：

• 第一行两个整数 $n,m$；
• 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

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

样例输入

4
5 10
2 4 2 4 2
3 50
12 2 3
2 40
6 35
2 5
1 5

样例输出

0
1
2
4

数据范围

对全部数据：

• $1\le T\le 10^5$；
• $1\le n\le 10^6$，$1\le m\le 5\cdot 10^6$；
• $1\le a_i\le m$；
• 所有测试数据的 $n$ 之和不超过 $10^6$；
• 所有测试数据的 $m$ 之和不超过 $5\cdot 10^6$。

每个测试点独立计分。