#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		vector<ll> a(n);
		for (auto &x : a) cin >> x;
		const int k = 2;
		vector dp(n, vector(2*k+1, LLONG_MAX));
		for (int i = -k; i <= k; ++i) dp[0][k+i] = 1LL << abs(i);
		for (int i = 1; i < n; ++i) {
			for (int j = -k; j <= k; ++j) {
				for (int jj = -k; jj <= k; ++jj) {
					ll x = a[i] + j, y = a[i-1] + jj;
					if (gcd(x, y) > 1) continue;
					if (dp[i-1][jj+k] == LLONG_MAX) continue;
					dp[i][j+k] = min(dp[i][j+k], dp[i-1][jj+k] + (1LL << abs(j)));
				}
			}
		}
		ll ans = LLONG_MAX;
		for (int i = 0; i <= 2*k; ++i) ans = min(ans, dp[n-1][i]);
		assert(ans < LLONG_MAX);
		cout << ans << '\n';
	}
}