黄
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}在神秘的魔法学院中，学员小黄偶然间获得了一串蕴含魔力的整数序列。这些整数各自拥有独特的魔力属性，然而，若相邻两个整数的魔力属性不能相互兼容（即不互质），就会引发魔力冲突，可能导致严重的魔法事故。
\hspace{15pt}为了避免魔力冲突，小黄可以施展魔法，选择序列中的一个整数，将其转化为任意一个大于 1 的整数，以此改变它的魔力属性。现在，小黄迫切想知道，最少需要施展多少次这样的魔法，才能让这串整数序列中的相邻元素魔力属性都相互兼容（即相邻元素都互质）。

【名词解释】
\hspace{15pt}互质：如果两个整数 a 和 b 的最大公约数为 1 那么就称 a 和 b 互质。最大公约数指的是能够同时整除这几个整数的最大正整数。例如 8,10 的最大公因数是 2，不是 1，因此不是互质。7, 13 的最大公因数是 1，因此这是互质。

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leq T\leq 10^5\right) 代表数据组数，每组测试数据描述如下： 
\hspace{15pt}第一行输入一个整数 n\left(2 \leq n \leq 10^5\right)，表示序列的长度。 
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots,a_n\left(1 \leq a_i \leq 10^{18}\right)，表示给定的整数序列。 

\hspace{15pt}除此之外，保证单个测试文件的 n 之和不超过 2\times10^5。

输出描述:

\hspace{15pt}对于每个查询，新起一行输出一个整数，表示使得序列中相邻元素互质所需的最小操作次数。如果无论如何修改都无法满足条件，输出 -1。
示例1

输入

复制 
4
5
2 4 6 9 12
2
2 2
4
2 3 5 7
5
1000000000000000000 2 7 3 12

输出

复制 
2
1
0
2