#include<iostream>
#include<ctime>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
int T,n;
int da[555],direct[555],vis[555],frie[555],tmp[555];
int ans,ju[] = {1111,1110,111,1,0,1001,110,1000};
bool isd(int a,int b,int c,int d){
    int jugd = 1000 * direct[a] + 100 * direct[b] + 10 * direct[c] + direct[d];
    bool ass = 0;
    for(int i = 0;i < 8;i++){
        if(jugd == ju[i]){
            ass = 1;
            break;
        }
    }
    return ass;
}
int getans(){
    int ans = 0;
    for(int i = 1; i <= n;++i){
        if((i+1 < frie[i] && frie[i] < frie[i+1] ) && isd(i,i+1,frie[i],frie[i+1]))
            ans++;
    }
    //cout<<"ans"<<ans<<endl;
    return ans;
}
void cop(int *myfrom, int *myto)
{
	int *from = myfrom;
	int *to = myto;
	while ((*to = *from) != -1)
	{
		from++; to++;
	}

	*to = -1;
}

void SA(){
    int t = 3000;
    while (t > 1e-15){
        for(int i = 1 ; i <= n;++i){
            if(vis[i]){continue;}
            int mi = rand() % 2,mi1 = rand() % 2;
            int j;
            for(j = 1; j <= n;j++)
                if(da[i] == da[j])
                    break;
            direct[i] = mi,direct[j]=mi1;
            frie[i] = j;
            frie[j] = i;
            vis[i] = 1;
            vis[j] = 1;
        }
        int tans = getans();
        int de = tans - ans;
        if(de < 0){
            ans = tans;
            cop(direct,tmp);
            memset(vis, 0, sizeof(vis));
        }else if(exp(-de/t)*RAND_MAX < rand()){
            cop(tmp,direct);
            memset(vis,0,sizeof(vis));
        }else{
            cop(direct, tmp);
            memset(vis, 0, sizeof(vis));
        }
        t*=0.997;
    }
}

int main(){
    ios::sync_with_stdio(0);
    srand(time(0));
    cin >> T;
    while(T--){
        memset(da, 0, sizeof(da));
        memset(frie, 0, sizeof(frie));
        memset(tmp, 0, sizeof(tmp));
        memset(direct, -1, sizeof(direct));
        memset(vis, 0, sizeof(vis));
        cin >> n;
        for(int i = 1; i <= n; ++i){
            cin >> da[i];
        }
        ans = getans();
        SA();
        SA();
        SA();
        SA();
        SA();
        SA();
        SA();
        SA();
        SA();
        SA();
        cout << ans << endl;
        ans = 0;
    }
    system("pause");
    return 0;
}