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