模拟 O(n)
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;

int gcd(int a, int b){
    return !b ? a : gcd(b, a % b);
}

void solve(){
    int n;
    cin >> n;
    std::vector<int>a(n + 1);
    for(int i = 1;i <= n;i++)cin >> a[i];
    std::vector<int>b(n);
    int bad = 0;
    for(int i = 1;i <= n - 1;i++)b[i] = gcd(a[i], a[i + 1]);        
    for(int i = 1;i < n - 1;i++)bad += b[i] > b[i + 1];
    // cout<< endl;
    // cout << bad << endl;
    bool ans = 0;
    if(bad == b[1] > b[2])ans = 1;
    if(bad == b[n - 2] > b[n - 1])ans = 1;
    for(int i = 2;i < n;i++){
        int tmp = bad;
        int g = gcd(a[i - 1], a[i + 1]);

        tmp -= b[i - 1] > b[i];
        if(i > 2){
            tmp -= b[i - 2] > b[i - 1];
            tmp += b[i - 2] > g;
        }

        if(i < n - 1){
            tmp -= b[i] > b[i + 1];
            tmp += g > b[i + 1];
        }

        if(tmp == 0){
            ans = 1;
        }
    }
    if(ans) cout << "YES" << endl;
    else cout << "NO" << endl;
}

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

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