今天我们来解决一个 NP-Hard 问题。

现有 $N$ 个物品，第 $i$ 个物品的大小为 $A_i$ ($1 \le A_i \le 12$)。你有若干个容量为 12 的箱子。当且仅当放入箱中的物品大小之和不超过 12 时，多个物品可以放入同一个箱子。

求装下所有 $N$ 个物品所需的最少箱子数量。

输入包含一个特殊限制： 1. 对于所有非样例测试文件，测试用例数量 $T$ 和物品数量 $N$ 是固定的（$T = 100, N = 1000$）。 2. 物品大小是随机生成的。具体而言，每个 $A_i$ 都是从区间 $[1, 12]$ 的整数集合中均匀独立随机选择的。

输入格式

• 输入的第一行包含一个整数 $T$，表示测试用例的数量。
• 每个测试用例包含两行输入：
  • 第一行包含 $N$，即物品的数量。
  • 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$，表示物品的大小。

输出格式

对于每个测试用例，输出一行，表示所需的最少箱子数量。

数据范围

对于所有非样例测试： $T = 100$ $N = 1000$ $1 \le A_i \le 12$ 每个 $A_i$ 都是在区间 $[1, 12]$ 内均匀随机生成的整数。

共有 19 个非样例测试。

样例

样例输入 1

10
5
8 2 2 3 9
3
11 1 1
8
9 8 2 3 4 2 2 12
10
2 2 2 2 2 2 3 3 3 3
6
5 2 8 4 1 11
8
12 12 9 8 2 8 4 4
5
5 5 6 6 6
8
10 12 5 4 8 2 2 11
7
5 1 5 7 9 4 4
6
12 1 1 9 3 5

样例输出 1

2
2
4
2
3
5
3
5
4
3

说明

测试用例 1：我们可以这样分配物品： 箱子 1：物品 1、2 和 3。它们的大小之和恰好为 12。 箱子 2：物品 4 和 5。它们的大小之和也恰好为 12。

因此，2 个箱子就足够了。