如果任何两个相邻元素中较大的元素不大于较小元素的两倍,则 Polycarp 称数组为密集的。更正式地说,对于任何 $$$i$$$ ($$$1 \le i \le n-1$$$),必须满足以下条件: $$$$$$\frac{\max(a[i], a[i+1])}{\min(a[i], a[i+1])} \le 2$$$$$$
例如,数组 $$$[1, 2, 3, 4, 3]$$$、$$$[1, 1, 1]$$$ 和 $$$[5, 10]$$$ 是稠密的。并且数组 $$$[5, 11]$$$, $$$[1, 4, 2]$$$, $$$[6, 6, 1]$$$ 并不稠密。
给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。要使数组变得稠密,您至少需要添加多少个数字?您可以在数组中的任意位置插入数字。如果数组已经很稠密,则无需添加数字。
例如,如果 $$$a=[4,2,10,1]$$$,那么答案是 $$$5$$$,插入元素后的数组本身可能如下所示: $$$a=[4,2,\underline{\textbf{3}},\underline{\textbf{5}},10,\underline{\textbf{6}},\underline{\textbf{4}},\underline{\textbf{2}},1]$$$(还有其他方法来构建这样的$$$a$$$)。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$)。然后是 $$$t$$$ 测试用例。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 50$$$) — 数组 $$$a$$$ 的长度。
下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 50$$$)。
输出
对于每个测试用例,输出一个整数 - 必须添加到数组以使其稠密的最小数字数。
示例
输入 #1
6 4 4 2 10 1 2 1 3 2 6 1 3 1 4 2 5 1 2 3 4 3 12 4 31 25 50 30 20 34 46 42 16 15 16
输出 #1
5 1 2 1 0 3
注意
第一个测试用例在语句中进行了解释。
在第二个测试用例中,您可以插入一个元素,$$$a=[1,\underline{\textbf{2}},3]$$$。
在第三个测试用例中,您可以插入两个元素,$$$a=[6,\underline{\textbf{4}},\underline{\textbf{2}},1]$$$。
在第四个测试用例中,您可以插入一个元素,$$$a=[1,\underline{\textbf{2}},4,2]$$$。
在第五个测试用例中,数组 $$$a$$$ 已经是稠密的。