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 i (1 ≤ i ≤ n-1), this condition must be satisfied: $$$(max(a[i], a[i+1]))/(min(a[i], a[i+1])) ≤ 2$$$

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

You are given an array a of n 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], then the answer is 5, and the array itself after inserting elements into it may look like this: a=[4,2,\underline{3},\underline{5},10,\underline{6},\underline{4},\underline{2},1] (there are other ways to build such a).

Input

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

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

The next line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 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


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


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,\underline{2},3].

In the third test case, you can insert two elements, a=[6,\underline{4},\underline{2},1].

In the fourth test case, you can insert one element, a=[1,\underline{2},4,2].

In the fifth test case, the array a is already dense.
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define N 500005
#define mod 1000000007
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i,a,b) for(int i=a;i<b;i++)
#define endl "\n"
#define PI 3.14159265358979323846  /* pi */
#define is_pot(n) (n&& !(n&(n-1)))
#define all(v)  ((v).begin()),((v).end())
#define degreesToRadians(angleDegrees) (angleDegrees * PI / 180.0) // Converts degrees to radians.
#define radiansToDegrees(angleRadians) (angleRadians * 180.0 / PI) // Converts radians to degrees.
#define int long long
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define epsilon 1e-9
typedef long long ll;
typedef long double ld;

int dx[]={1, 0, -1, 0};
int dy[]={0, 1, 0, -1};

void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
/*

1. Edge cases are killer.
2. Clear global variables while multiple tcs.
3. Be relax... Rating is just a number.

*/




















void solve()
{
	int n;
	cin>>n;
	int a[n];
	rep(i, n)
		cin>>a[i];
	int ans=0;
	for(int i=1;i<n;i++)
	{
		int mx=max(a[i], a[i-1]);
		int mn=min(a[i], a[i-1]);
		// cout<<mx<<" "<<mn<<endl;
		if((mx/mn)+(mx%mn!=0)>2)
		{
			int cnt=0;
			while(mn<mx)
			{
				mn*=2;
				cnt++;
			}
			ans+=cnt-1;
		}
	}
	cout<<ans<<endl;
}
 
signed main() {

   	fastio

    	int t;cin>>t;while(t--)
	    solve();
 
 
return 0;
}