题目描述

给定一个元素全为正整数的序列 $A_1, A_2, \dots, A_n$。你要进行多次操作，使序列的元素全为零。

对于每次操作，你都可以指定任意一个长度为 $m$ 的序列

$$B_1, B_2, \dots, B_m \quad (B_i \in \{1, 2, \dots, n\})$$

，并分别将 $A_{B_i}$ 减去 $2^{i-1}$。

求使给定序列全为零的最小操作次数。

输入格式

• 第一行包含一个整数 $T$（$1 \le T \le 1000$），表示测试数据的组数。
• 对于每个测试数据：
  • 第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示给定序列的长度。
  • 第二行包含 $n$ 个整数 $A_1, A_2, \dots, A_n$（$1 \le A_i \le 10^9$），表示给定序列。
    可以保证 $\sum n \le 10^5$。

输出格式

• 对于每个测试数据：
  输出一行，其中包含一个整数，表示答案。

样例

3
5
1 2 3 4 5
2
1 4
1
7

3
3
1

样例 1 解释

对于第一个样例，有一种可能的方案：

1. 指定 $B = \{1, 3, 5\}$，操作后，$A$ 变为 $\{0, 2, 1, 4, 1\}$。
2. 指定 $B = \{3, 2, 4\}$，操作后，$A$ 变为 $\{0, 0, 0, 0, 1\}$。
3. 指定 $B = \{5\}$，操作后，$A$ 变为 $\{0, 0, 0, 0, 0\}$。

对于第二个样例，有一种可能的方案：

1. 指定 $B = \{1, 2\}$，操作后，$A$ 变为 $\{0, 2\}$。
2. 指定 $B = \{2\}$，操作后，$A$ 变为 $\{0, 1\}$。
3. 指定 $B = \{2\}$，操作后，$A$ 变为 $\{0, 0\}$。

对于第三个样例，有一种可能的方案：

1. 指定 $B = \{1, 1, 1\}$，操作后，$A$ 变为 $\{0\}$。

数据范围

对于全部的数据，
$1 \le T \le 1000$，
$1 \le n \le 10^5$，
$1 \le A_i \le 10^9$，
$\sum n \le 10^5$。