邻合

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

题目描述

$\hspace{15pt}$ 小苯有一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$ ，每个元素都是正整数。
$\hspace{15pt}$ 小苯每次操作可以选择序列中的一个元素 $a_i$ ，将其替换为任意正整数。

$\hspace{15pt}$ 小苯想知道，最少需要修改多少个元素（可以不修改），才能使得序列 $a$ 满足：任意相邻的元素都不是互质的。
$\hspace{15pt}$ 你的任务就是求出这个最小修改次数。

【名词解释】
$\hspace{15pt}$ 互质：多个整数的最大的共有约数（简称最大公约数，gcd）如果恰好为 $1$ ，被称它们为互质的。例如， $12$ 和 $30$ 的公约数有 $1,2,3,6$ ，其中最大的约数是 $6$ ，所以它们不是互质的； $5$ 和 $7$ 的公约数仅有 $1$ ，所以它们是互质的。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行输入一个整数 ，表示序列的长度。
第二行输入  个正整数 ，表示序列的元素。
除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示最小修改次数。

示例1

输入

复制

3
5
2 3 6 1 10
4
2 2 2 2
6
6 1 5 6 2 15

输出

复制

2
0
3

说明

对于第一组测试数据，初始序列为 ，相邻 GCD 依次为 。其中一种最优方案是，修改第  个元素为 ，第  个元素为 ，得到 ，这样一来相邻元素均不互质。