题目描述

给定 $n$ 个木棍，第 $i$ 个长度为 $a_i$。

你需要保证：

• 构成的任意多边形每一边由一根木棍构成。

• 没有木棍用于多个多边形的边。

求通过这些木棍同时能构造的正多边形数量。

注：不可以破坏木棍。

输入格式

第一行一个整数 $t$，表示数据组数。

接下来对于每组数据，第一行一个整数 $n$。

接下来 $n$ 个整数，表示 $a_i$。

输出格式

共 $t$ 行，每行一个整数，表示答案。

说明/提示

对于第一组数据，显然一根木棍无法构造多边形。

对于第二组数据，显然两根木棍也无法构造多边形。

对于第三组数据，可以用四根长度为 $3$ 的木棍构造一个正方形。

对于第四组数据，可以用五根长度为 $2$ 的木棍构造一个五边形，然后用四根长度为 $4$ 的木棍构造一个正方形。

对于全部数据，满足 $1\le t,n,a_i\le100$。

样例

4
1
1
2
1 1
6
2 2 3 3 3 3
9
4 2 2 2 2 4 2 4 4

0
0
1
2