题目背景

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

题目描述

淇宝有一个由正整数构成的大小为 $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$ 的最小值。

3
4
1 2 3 4
5
3 3 4 5 5
6
4 6 12 13 26 39

0
2
1

提示

样例解释

第一组数据的最优解 $S=\{2,3,4\},T=\{1\}$。

第二组数据存在一组最优解 $S=\{4,5,5\},T=\{3,3\}$。

第三组数据的最优解 $S=\{13,26,39\},T=\{4,6,12\}$。

数据规模与约定

本题采用捆绑测试。

对于所有数据，$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$。

部分数据点输入数据较大，请使用较为快速的读入方式。