你有 $n$ 个盒子，大小分别为 $a_1, a_2, \dots, a_n$。所有盒子的大小均为 2 的幂。在一个大小为 $r$ 的盒子中，你可以放入总大小不超过 $\frac{r}{2}$ 的其他盒子（同样地，在这些盒子中，你还可以放入其他盒子，以此类推）。无论内部的包装结构如何，盒子本身的大小保持不变。

你的任务是规划如何嵌套这些盒子，使得没有被放入任何其他盒子中的盒子数量最少。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 500\,000$)，表示测试用例的数量。接下来的 $2t$ 行描述了这些测试用例，每个测试用例包含两行。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 100\,000$)，表示盒子的数量。

每个测试用例的第二行包含一个由 $n$ 个整数组成的序列 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{12}$；$a_i$ 为 2 的非负整数次幂)，表示各个盒子的大小。

所有测试用例的 $n$ 之和不超过 $500\,000$。

输出格式

输出应包含 $t$ 行，每行包含一个整数。第 $i$ 行的数字应表示第 $i$ 个测试用例中，最少可能的外部（即没有被装入任何其他盒子）盒子数量。

样例

输入 1

4
5
1 2 1 1 8
3
1 1 1
6
1 1 1 4 1 2
3
8 4 2

输出 1

1
3
3
1

说明

样例中的最优盒子包装方式如下所示。

在第一个测试用例中：

在第二个测试用例中：

在第三个测试用例中：

在第四个测试用例中：