题目描述

在古老的魔法学院中，收藏着两种珍贵的魔法宝石：红色宝石（能量值为1）和蓝色宝石（能量值为2）。

学院里收藏的宝石，每种至少会收藏1颗。宝石总数为n（2≤n≤200）。

任务要求：作为学院的宝石管理员，你需要将这n颗宝石分成尽可能多的魔法阵（m份）， 要求：

（1）每个魔法阵中的宝石能量总和必须相同；

（2）每个魔法阵必须至少包含2颗宝石。

目标是求出可以组成的最大魔法阵数量m。

输入格式

第一行，一个整数g，表示有g组测试数据（g≤5）。

接下来每组数据有两行：

第一行：宝石总数n，

第二行：n个数字（1或2），表示每颗宝石的能量值。

输出格式

输出g行，每行一个整数，表示可以组成的最大魔法阵数量。

输入/输出例子1

1
4
1 1 2 2

2

样例解释

【样例解释】

可以分成2组，每组的能量值是3。