有$$$n$$$块陈皮,其中第$$$i$$$的大小为$$$a_i$$$。在一步中,可以将一块尺寸 $$$x$$$ 分成两块正整数尺寸 $$$y$$$ 和 $$$z$$$,使得 $$$y + z = x$$$。
您希望每对零件的尺寸相差严格小于两倍。换句话说,不应该有两个大小为 $$$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
3 5 1 2 3 4 5 1 1033 5 600 900 1300 2000 2550
输出 #1
10 0 4
注意
在第一个测试用例中,我们最初有一个大小为 $$$1$$$ 的片段,因此所有最终片段的大小必须为 $$$1$$$。总步数为:$$$0 + 1 + 2 + 3 + 4 = 10$$$。
在第二个测试用例中,我们只有一件,所以我们不需要做任何事情,答案是 $$$0$$$ 步骤。
在第三个测试用例中,可能的剪切选项之一是:$$$600,\ 900,\ (600 | 700),\ (1000 | 1000),\ (1000 | 1000 | 550)$$$。您可以在下图中看到此选项。最大件的尺寸为$$$1000$$$,并且比最小件的尺寸$$$550$$$大不到$$$2$$$倍。 $$$4$$$ 步骤已完成。我们可以证明这是最小可能的步骤数。