题目描述

你有一个长度均为 $n$ 的正整数数组 $a$。可以执行以下操作任意次（也可以不执行）：

• 选择一个整数 $a_i$ 其中 $i\in [1,n]$，令 $a_i\gets a_i+1$，这样做的代价为 $1$。

问最少操作多少次，使得在数组 $a$ 中存在两个整数 $i,j$ 满足：

• $1\leq i<j\leq n$。
• 且 $\gcd(a_i,a_j)>1$。

求最少操作次数。

输入格式

本题有多组数据

第一行输入一个整数 $t$ 表示测试数据组数，每一组数据：

• 第一行输入一个整数 $n$ 表示数组的长度。
• 第二行输入 $a_1,a_2,\ldots,a_n$。

保证 $\sum n\leq 2\times 10^5$。

输出格式

对于每一组数据，输出一个整数代表答案。

6
2
1 1
2
4 8
5
1 1 727 1 1
2
3 11
3
2 7 11
3
7 12 13

2
0
2
1
1
1

提示

样例 1 解释

在一组数据中，可以令 $a_1,a_2$ 分别各操作 $1$ 次使得 $a_1=a_2=2$，此时满足 $\gcd(a_1,a_2)=2>1$。

在第二组数据中，$\gcd(a_1,a_2)=4>1$ 因此不需要操作。

数据范围

对于 $100\%$ 的数据满足：$1\leq t\leq 10^4$，$2\leq n\leq 2\times 10^5$，$1\leq a_i\leq 2\times 10^5$，且 $\sum n\leq 2\times 10^5$。