思路分析

我们希望 尽可能快地让 $a_1$ 成为最大值。直觉上，每次应该从当前最大的 $a_i$ （$i \ge 2$）转移值到 $a_1$，这样 $a_1$ 增长最快，其他元素尽快下降。

因此可以：

1. 将 $a_2, \dots, a_n$ 放入一个最大堆（优先队列）。
2. 每次取堆顶最大值 $m$（对应某个 $a_j$）。
3. 计算 $x = \lfloor m/2 \rfloor$，执行转移操作。
4. 将更新后的 $a_j$ 放回堆中（如果还大于 0）。

题目内容

给定正整数 $n$ 和一个大小为 $n$ 的数组。小种可以对这个数组执行若干次以下操作:选择一个下标 $i$ 令 $x=[\frac{a_i}{2}]$ (即向下取整)，令$a_1=a_1+x,a_i=a_i-x$ 。

小钟需要求出最少的操作次数使得 $a_i$ 成为数组中最大的元素，即对于任意的 $i(2 <=i<=n)$ 满足 $a_i<a_1$ 。题目保证给定数据一定存在答案。

请你计算出最少的操作次数是多少。

输入描述

输入包括多组测试数据。

输入第一行包括一个正整数 $T(1<=T<=100)$ ，表示测试数据的组数。

每组测试数据的第一行有一个整数 $n(1 <=n<=10^5)$ ，表示数组的大小;

接下来的一行有 $n$ 个整数 $a_1,a_2,…,a_n(2 <=a_i<=10^9)$ ，表示题目给定的数组。

保证每个测试点的所有测试数据的 $n$ 的和不超过 $2*10^5$ 。

输出描述

对于每组测试数据，输出一个正整数表示使得 $a_i$，成为最大元素的最少的操作次数。

样例1

输入

2
3
2 4 5
2
3 2

输出

2
0

说明

对于第一组测试数据，可以选择下标$3$，数组变为$[4,4,3]$，然后选择下标$2$，数组变为$[6,2,3]$,此时$a_1$是数组中最大的元素，操作次数为$2$。可以证明不存在更少的操作次数使得$a_1$成为最大的元素。

对于第二组测试数据,由于$a_1$本来就已经是最大元素，故不需要进行任何操作。