题目描述

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]$（当然还有其他构造方式）。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。

接下来每个测试用例包含两行。

第一行包含一个整数 $n$（$2 \le n \le 50$），表示数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 50$）。

输出格式

对于每个测试用例，输出一个整数，表示最少需要插入多少个数才能使数组变为稠密。

说明/提示

第一个测试用例的解释见题面。

第二个测试用例，你可以插入一个元素，$a=[1,\underline{\textbf{2}},3]$。

第三个测试用例，你可以插入两个元素，$a=[6,\underline{\textbf{4}},\underline{\textbf{2}},1]$。

第四个测试用例，你可以插入一个元素，$a=[1,\underline{\textbf{2}},4,2]$。

第五个测试用例，数组 $a$ 已经是稠密的。

由 ChatGPT 4.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

5
1
2
1
0
3