P11694 [JRKSJ ExR] 淇宝的划分

题目中人名纯属虚构，如有雷同纯属巧合。

淇宝有一个由正整数构成的大小为 $n$ 的可重集 $A$，他想把这个可重集划分成两部分 $S,T$。具体地，非空可重集 $S,T$ 满足任意正整数 $v$ 在 $S,T$ 中的出现次数之和等于其在 $A$ 中的出现次数。 淇宝作为举世闻名的全世界最年轻获得 LGM（LCM and GCD Master）的选手，计算出了 $\gcd_{v\in S}v$ 和 $\operatorname{lcm}_{v\in T}v$。 现在他希望你求出所有划分方案中，$\lvert(\gcd_{v\in S}v)-(\operatorname{lcm}_{v\in T}v)\rvert$ 的最小值。

**本题包含多组测试数据。** 第一行一个正整数 $T$ 表示测试数据组数。 对于每组测试数据： 第一行一个正整数 $n$，表示可重集的大小。 第二行 $n$ 个正整数 $a_{1\sim n}$ 表示可重集 $A$ 内的元素。保证 $a_1\leq a_2\leq\dots\leq a_n$。

对于每组测试数据，输出一行，一个非负整数，表示 $\lvert(\gcd_{v\in S}v)-(\operatorname{lcm}_{v\in T}v)\rvert$ 的最小值。

### 样例解释 第一组数据的最优解 $S=\{2,3,4\},T=\{1\}$。 第二组数据存在一组最优解 $S=\{4,5,5\},T=\{3,3\}$。 第三组数据的最优解 $S=\{13,26,39\},T=\{4,6,12\}$。 ### 数据规模与约定 **本题采用捆绑测试。** | $\text{Subtask}$ | $n\leq$ | $\sum n\leq$ | $a_i\leq$ | 分数 | |:--:|:--:|:--:|:--:|:--:| | $1$ | $16$ | $100$ | $10^{18}$ | $6$ | | $2$ | $300$ | $3\times10^3$ | $100$ | $19$ | | $3$ | $2\times10^4$ | $2\times10^5$ | $10^6$ | $13$ | | $4$ | $2\times10^4$ | $2\times10^5$ | $10^9$ | $15$ | | $5$ | $2\times10^5$ | $2\times10^6$ | $10^9$ | $22$ | | $6$ | $10^6$ | $5\times10^6$ | $10^{18}$ | $25$ | 对于所有数据，$1\leq T\leq10^4$，$2\leq n\leq10^6$，$\sum n\leq5\times10^6$，$1\leq a_i\leq10^{18}$，$a_1\leq \dots\leq a_n$。 **部分数据点输入数据较大，请使用较为快速的读入方式。**