魔力共鸣：最小公倍数的融合

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

题目描述

$\hspace{15pt}$ 炼金术士 awdec 正在研究一种古老的魔法晶石。他面前摆放着一排共 $n$ 颗晶石，每颗晶石内部都蕴含着特定数值的魔力。
$\hspace{15pt}$ 根据炼金术的法则，如果存在一种纯粹的魔法元素（即所有晶石魔力值的最大公约数严格大于 $1$ ），这些晶石就会产生“魔力共鸣”。
$\hspace{15pt}$ 为了引发共鸣，awdec 掌握了一种融合技术：他可以将两颗晶石融合成一颗更强大的晶石。你能帮他计算出，最少需要融合几次才能让剩下的晶石产生共鸣吗？

$\hspace{15pt}$ 给定一个长度为 $n$ 的正整数序列 $a$ ，代表初始时每颗晶石的魔力值。
$\hspace{15pt}$ 你可以执行以下操作任意次（也可以不执行）：
$\hspace{23pt}\bullet$ 选择序列中两个不同位置的元素 $a_i,a_j\left(i\ne j\right)$ 。
$\hspace{23pt}\bullet$ 将这两个元素从序列中删除。
$\hspace{23pt}\bullet$ 向序列中插入一个新的元素，其值为 $\operatorname{lcm}\left(a_i,a_j\right)$ 。
$\hspace{15pt}$ 你的目标是使得最终序列中所有元素的最大公约数不为 $1$ 。
$\hspace{15pt}$ 请计算最少需要进行多少次操作。如果无论如何操作都无法满足条件，请输出 $-1$ 。

【名词解释】
$\hspace{15pt}$ 最小公倍数（lcm）：指两个或多个整数公有的倍数中最小的一个。例如， $8$ 和 $12$ 的最小公倍数是 $24$ ，因此记作 $\operatorname{lcm}(8,12)=24$ 。
$\hspace{15pt}$ 最大公约数（gcd）：指两个或多个整数共有约数中最大的一个。例如， $12$ 和 $30$ 的公约数有 $1,2,3,6$ ，其中最大的约数是 $6$ ，因此记作 $\gcd(12,30)=6$ 。特别地，单个整数的 $\gcd$ 定义为其自身。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行包含一个正整数 ，表示初始序列的长度。
第二行包含  个正整数 ，分别表示序列中每个元素的初始值。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每组测试数据，输出一行一个整数，表示达成目标所需的最少操作次数；如果不可能使得序列的所有数最大公约数不为 ，输出 。

示例1

输入

复制

2
6
1 1 4 5 1 4
6
1 9 1 9 8 10

输出

复制

4
4

说明

在第一组测试数据中，初始序列为 。一种最优的  次操作方案如下：
 选择  和 ，融合为 ，序列变为 。
 选择  和 ，融合为 ，序列变为 。
 选择  和 ，融合为 ，序列变为 。
 选择  和 ，融合为 ，序列变为 。
 此时，剩余元素的所有数最大公约数 ，满足条件。可以证明没有比  次更少的操作方案。