问题描述

小C很喜欢质数，因为质数的因子只有两个，很简单。这一天小C发现了 $n$ 个数字，他无法容忍相邻的两个数字之间不是互质的，所以他动用了超能力，这个能力可以修改数组中的任意一个数，使其改成任意一个大于 $1$ 的数。现在小C想知道他至少需要使用几次超能力，才能使得数组中任意相邻的两个数都是互质的。

两个数互质：即两个数的最大公约数为 $1$。

输入格式

输入的第一行包含一个正整数 $T$ $(1 \leq T \leq 10)$，表示数据组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

• 第一行两个正整数 $n(1\le n \le 10^5)$，表示数组的长度。
• 第二行 $n$ 个正整数 $a_i(1\le a_i \le 10^9)$。

输出格式

对于每组数据，输出一个整数，表示使得序列中相邻元素互质所需的最小操作次数。如果无论如何修改都无法满足条件，输出 -1。

样例输入

4
5
2 4 6 9 12
2
2 2
4
2 3 5 7
5
1000000 2 7 3 12

样例输出

2
1
0
2