1362:互质问题

有一堆数字排成一排，涂涂希望删除其中尽可能少的数字后，就能满足任意相邻的两个数字都是互质的（最大公因数为1），问最少需要删除几个数字？

多组案例。一个正整数n，表示案例的数量。（n<=20）

每组案例中，先是一个正整数m，表示数字的数量，（2<=m<=2000）

然后是m个正整数，每个数字都不大于100万。

针对每组案例，输出一个整数，表示最少需要删除的数字数量。

每组案例输出完都要换行。

3

5

1 2 3 4 5

5

2 4 6 8 10

6

2 6 3 9 2 6

0

4

3

第一组案例，任意两个相邻的数字都是互质的。

第二组案例，由于正偶数之间不互质，所以必须得删除其中4个，剩下任意一个。

第三组案例，在删除6、9、6这三个数字后能满足要求。