题目描述

有 $n$ 块橘子皮，第 $i$ 块的大小为 $a_i$。每一步可以将一块大小为 $x$ 的橘子皮分成两块正整数大小的橘子皮 $y$ 和 $z$，满足 $y + z = x$。

你希望对于任意两块橘子皮，它们的大小之比严格小于 $2$。换句话说，不存在两块大小分别为 $x$ 和 $y$ 的橘子皮，使得 $2x \le y$。请问最少需要多少步才能满足上述条件？

输入格式

输入的第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 100$）。

接下来一行包含 $n$ 个整数 $a_1 \le a_2 \le \ldots \le a_n$（$1 \le a_i \le 10^7$）。

输出格式

对于每个测试用例，输出一行，表示最少需要的步数。

说明/提示

在第一个测试用例中，初始有一块大小为 $1$ 的橘子皮，因此所有最终的橘子皮都必须为 $1$。总共需要的步数为：$0 + 1 + 2 + 3 + 4 = 10$。

在第二个测试用例中，只有一块橘子皮，无需操作，答案为 $0$ 步。

在第三个测试用例中，一种可能的切法为：$600,\ 900,\ (600 | 700),\ (1000 | 1000),\ (1000 | 1000 | 550)$。你可以在下图中看到这种切法。最大的一块为 $1000$，且小于最小一块 $550$ 的 $2$ 倍。共进行了 $4$ 步。可以证明这是最少的步数。

由 ChatGPT 4.1 翻译

样例

3
5
1 2 3 4 5
1
1033
5
600 900 1300 2000 2550

10
0
4