#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; }