题目描述

今天，哥萨克胡子遇到了他的老朋友——哥萨克耳朵。他们聊了很久，回忆了各自的童年和青年时光。话题也引到了当年他们在编程奥林匹克竞赛中未能解决的一道题。

给定一个包含 $n$ 个数的数组。每次操作可以选择其中一个数 将其增加 $1$。你需要确定，最少需要多少次操作，才能使得到的数组满足以下条件：

• 对于所有 $i$ 从 $1$ 到 $n-1$，满足 $a_i \le a_{i+1}$。
• 所有数的最大公约数大于 $1$。

最大公约数 指的是一组正数中，能同时整除所有数的最大正整数。

输入格式

第一行包含一个整数 $t$ $(1\leq t\leq 5)$ —— 测试用例的数量。接下来是每个测试用例的描述。

每个测试用例描述的第一行包含一个整数 $n$ ($1\leq n\leq 10^4$) —— 数组的大小。

每个测试用例描述的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1\leq a_i\leq 10^4)$ —— 数组中的数。

输出格式

对于每个测试用例，在单独一行输出一个数字 —— 为使数组满足给定条件所需的最少操作次数。

1
3
9 1 16

10

2
4
5 7 3 6
5
4 2 8 16 10

7
8

提示

在第一个样例中，可以将第一个和第二个数增加到 $10$，此时数组中所有数的最大公约数将等于二。

在第二个样例的第一个测试用例中，可以将所有数都变为 $7$。

在第二个样例的第二个测试用例中，可以将数组修改为 $[4, 4, 8, 16, 16]$。

$$\begin{array}{|c|c|c|c|} \hline \rule{0pt}{1.5em} \textbf{子任务编号} & \textbf{限制条件} & \textbf{额外限制} & \textbf{分值} \\ \hline \rule{0pt}{1.5em} 1 & 1 \leq n \leq 10^4 & 所有数为偶数 & 10 \\ \hline \rule{0pt}{1.5em} 2 & 1 \leq n \leq 10 & - & 20 \\ \hline \rule{0pt}{1.5em} 3 & 1 \leq n \leq 10^3 & - & 30 \\ \hline \rule{0pt}{1.5em} 4 & 1 \leq n \leq 10^4 & - & 40 \\ \hline \end{array}$$