#include <bits/stdc++.h>
using namespace std;

#define ll                   long long
ll binpow(ll a,ll b,ll p){
    if(b==0)return 1;
    ll t=binpow(a,b/2,p);
    if(b%2)return (((a*t)%p)*t)%p;
    else return ((t*t)%p);
}
void solve()
{
    int n;
    cin >> n;
    int a[n];
    for(int i = 0; i<n; i++)cin >> a[i];
    int k = 23;
    vector<vector<long long>> dp(k,vector<long long>(n,1e18));
    for(int i = 0; i<k; i++)
    {
		int bi = a[0]+i-16;
		if(bi<0)continue;
		dp[i][0] = min(dp[i][0],binpow(2,abs(a[0]-bi),1e18));
	}
	for(int i = 1; i<n; i++)
	{
		for(int j = 0; j<k; j++)
		{
			int bi = a[i]+j-16;
			if(bi<0)continue;
			ll x = binpow(2,abs(bi-a[i]),1e12);
			for(int l = 0; l<k; l++)
			{
				int ci = a[i-1]+l-16;
				if(ci<0)continue;
				
				if(__gcd(bi,ci)==1)
				{
					dp[j][i] = min(dp[j][i],dp[l][i-1]+x);
				}
			}
		}
	}
	ll ans = 1e18;
	for(int i = 0; i<k; i++)ans = min(ans,dp[i][n-1]);
	cout << ans << "\n";
}


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
    int t = 1;
     cin>> t;
    for(int i = 1; i<=t; i++) {
       solve();



   }
   return 0;
}