time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Polycarp calls an array dense if the greater of any two adjacent elements is not more than twice bigger than the smaller. More formally, for any ii (1≤i≤n−11≤i≤n−1), this condition must be satisfied:

max(a[i],a[i+1])min(a[i],a[i+1])≤2max(a[i],a[i+1])min(a[i],a[i+1])≤2

For example, the arrays [1,2,3,4,3][1,2,3,4,3], [1,1,1][1,1,1] and [5,10][5,10] are dense. And the arrays [5,11][5,11], [1,4,2][1,4,2], [6,6,1][6,6,1] are not dense.

You are given an array aa of nn integers. What is the minimum number of numbers you need to add to an array to make it dense? You can insert numbers anywhere in the array. If the array is already dense, no numbers need to be added.

For example, if a=[4,2,10,1]a=[4,2,10,1], then the answer is 55, and the array itself after inserting elements into it may look like this: a=[4,2,3––,5––,10,6––,4––,2––,1]a=[4,2,3_,5_,10,6_,4_,2_,1] (there are other ways to build such aa).

Input

The first line contains one integer tt (1≤t≤10001≤t≤1000). Then tt test cases follow.

The first line of each test case contains one integer nn (2≤n≤502≤n≤50) — the length of the array aa.

The next line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤501≤ai≤50).

Output

For each test case, output one integer — the minimum number of numbers that must be added to the array to make it dense.

Example

input

Copy

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

output

Copy

5
1
2
1
0
3

Note

The first test case is explained in the statements.

In the second test case, you can insert one element, a=[1,2––,3]a=[1,2_,3].

In the third test case, you can insert two elements, a=[6,4––,2––,1]a=[6,4_,2_,1].

In the fourth test case, you can insert one element, a=[1,2––,4,2]a=[1,2_,4,2].

In the fifth test case, the array aa is already dense.

 

解题说明：此题是一道数学题，为了保证连续两个数最大值不超过最小值的2倍，首先比较两个数大小，然后看相差多少倍，使用ceil函数求解。

#include<stdio.h>
#include<math.h>
int main()
{
	int t, n;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d", &n);
		long long int a[51], k = 0;
		scanf("%lld", a);
		for (int i = 0; i<n - 1; i++)
		{
			scanf("%lld", a + i + 1);
			if (a[i + 1] > a[i])
			{
				k += ceil(log10((float)a[i + 1] / a[i]) / log10(2) - 1);
			}
			else if (a[i + 1] < a[i])
			{
				k += ceil(log10((float)a[i] / a[i + 1]) / log10(2) - 1);
			}
		}
		printf("%lld\n", k);
	}
	return 0;
}