你的一半归我了

题目描述

给定一个大小为 $n$ 的数组 $a$。你可以执行任意次下述操作：

• 选择一个下标 $i$ ($2 \le i \le n$)
• 令 $x = \lfloor \frac{a_i}{2} \rfloor$
• 更新 $a_1 \leftarrow a_1 + x$，$a_i \leftarrow a_i - x$

你的目标是使得 $a_1$ 成为数组中唯一的最大元素，即对于任意 $i \in [2, n]$，都满足 $a_i < a_1$。

请求出达成该目标所需的最少操作次数。题目保证给定数据一定有解。

输入格式

输入包含多组测试数据。

第一行包含一个正整数 $T$，表示测试数据的组数。

对于每组测试数据： 第一行包含一个正整数 $n$，表示数组的大小。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$。

输出格式

对于每组测试数据，输出一行一个整数，表示最少的操作次数。

样例

样例输入

2
3
2 4 5
2
3 3

样例输出

2
1

提示

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le T \le 100$
• $1 \le n \le 10^5$
• $\sum n \le 2 \times 10^5$ (所有测试数据的 $n$ 之和不超过 $2 \times 10^5$)
• $2 \le a_i \le 10^9$