题目描述

制图之体有六，缺一不可言精。复设五等之制，以解天下土崩之势。

上图是三国杀操作难度最高的武将裴秀，由于其复杂的技能机制，经常被将军们称为数学家。 由于原版技能过于复杂，所以以下作为技能简化，当玩家每次出牌时，如果与上一张牌的点数有共同的大于$1$因子，那么可以摸一张牌，获得除初始手牌以外的牌称为过牌。 现在给定你的初始手牌，请你以任意顺序出牌，使得过牌量最大，并输出这个最大过牌量。

输入格式

第一行输入一个正整数$t$($1 \le t \le 10^4$)，表示多测试用例。

每组测试用例中，先输入一个正整数$n$($1 \le n \le 1e6$), 表示初始手牌的数量。

然后输入$n$ 个正整数$a_1, a_2, \ldots, a_n$($1 \le a_i \le 13$),表示每张牌的点数。

输出格式

一个正整数表示答案，最大过牌数量。

样例

2
5
1 2 8 2 3
3
2 6 9

2
2