t = int(input())
for i in range(t):
    n = int(input())
    s = list(input().split())
    s = "".join(s)
    if "101" in s:
        print('NO')
    else:
        print('YES')

for _ in range(int(input())):
    n, m = map(int, input().split())
    a = [list(map(int, input().split())) for i in range(n)]
    hasColor = [0] * (n * m)
    hasBad = [0] * (n * m)
    for i in range(n):
        for j in range(m):
            hasColor[a[i][j] - 1] = 1
            if i + 1 < n and a[i][j] == a[i + 1][j]:
                hasBad[a[i][j] - 1] = 1
            if j + 1 < m and a[i][j] == a[i][j + 1]:
                hasBad[a[i][j] - 1] = 1
    print(sum(hasColor) + sum(hasBad) - 1 - max(hasBad))

#include <bits/stdc++.h>
 
using namespace std;

const int MOD = 998244353;

int add(int x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
  return x;
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> dp(4, 0);
    dp[0] = 1;
    while (n--) {
      int x;
      cin >> x;
      if (x == 2) dp[x] = add(dp[x], dp[x]);
      dp[x] = add(dp[x], dp[x - 1]);
    }
    cout << dp[3] << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    int n = s.size();
    int i = 0;
    while (i < n / 2 && s[i] == s[n - i - 1]) ++i;
    n -= 2 * i;
    s = s.substr(i, n);
    int ans = n;
    for (int z = 0; z < 2; ++z) {
      int l = 0, r = n;
      while (l <= r) {
        int m = (l + r) / 2;
        vector<int> cnt(26);
        for (int i = 0; i < m; ++i)
          cnt[s[i] - 'a']++;
        bool ok = true;
        for (int i = 0; i < min(n / 2, n - m); ++i) {
          char c = s[n - i - 1];
          if (i < m) {
            ok &= cnt[c - 'a'] > 0;
            cnt[c - 'a']--;
          } else {
            ok &= (c == s[i]);
          }
        }
        for (auto x : cnt)
          ok &= (x % 2 == 0);
        if (ok) {
          r = m - 1;
        } else {
          l = m + 1;
        }
      }
      ans = min(ans, r + 1); 
      reverse(s.begin(), s.end());
    }
    cout << ans << '\n';
  }
}

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

typedef long long li;

template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
	return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
	fore(i, 0, sz(v)) {
		if(i) out << " ";
		out << v[i];
	}
	return out;
}

const int INF = int(1e9);
const li INF64 = li(1e18);

string s;
int a, b, ab, ba;

inline bool read() {
	if(!(cin >> s))
		return false;
	cin >> a >> b >> ab >> ba;
	return true;
}

int process(vector<int> &rem, int &tot) {
	int placed = 0;
	sort(rem.begin(), rem.end(), greater<int>());
	while (!rem.empty() && tot > 0) {
		int cnt = min(rem.back() / 2, tot);
		placed += cnt;
		tot -= cnt;
		rem.back() -= 2 * cnt;
		if (rem.back() == 0)
			rem.pop_back();
	}
	return placed;
}

int remnants(vector<int> &rem, int &tot) {
	int placed = 0;
	for (int &cur : rem) {
		int cnt = min(tot, (cur - 2) / 2);
		placed += cnt;
		tot -= cnt;
		cur -= 2 * cnt + 2;
	}
	return placed;
}

inline void solve() {
	s.push_back(s.back());
	int eq = 0, placedPairs = 0;
	vector<int> remAB, remBA;

	int lst = 0;
//	cerr << "s = " << s << endl;
	fore (i, 1, sz(s)) {
		if (s[i] != s[i - 1])
			continue;
		
		if (s[lst] == s[i - 1]) {
			// ABA..A or BAB..B
			eq += (i - lst) / 2;
		}
		else {
			int len = i - lst;
			if (s[lst] == 'A') {
				// ABA..B
				remAB.push_back(len);
			}
			else {
				// BAB..A
				remBA.push_back(len);
			}
		}
//		cerr << lst << ", " << i << endl;
		lst = i;
	}
	s.pop_back();
	
	placedPairs += process(remAB, ab);
	assert(remAB.empty() || ab == 0);

	placedPairs += process(remBA, ba);
	assert(remBA.empty() || ba == 0);

	placedPairs += remnants(remAB, ba);
	placedPairs += remnants(remBA, ab);

	int remPlaced = min(eq, ab + ba);
	placedPairs += remPlaced;

	int needA = count(s.begin(), s.end(), 'A') - placedPairs;
	int needB = count(s.begin(), s.end(), 'B') - placedPairs;

	if (needA <= a && needB <= b)
		cout << "YES\n";
	else
		cout << "NO\n";
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	int t; cin >> t;
	while (t--) {
		read();
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;             

const int N = 400043;
const int BUF = N * 20;

int* where[BUF];
int val[BUF];
int cur = 0;

void change(int& x, int y)
{
    val[cur] = x;
    where[cur] = &x;
    x = y;
    cur++;
}

void rollback()
{
    cur--;
    (*where[cur]) = val[cur];
}

struct DSU
{
    vector<int> p, s;
    int n;
    int comps;

    int get(int x)
    {
        if(p[x] == x) return x;
        return get(p[x]);
    }

    void merge(int x, int y)
    {
        x = get(x);
        y = get(y);
        if(x == y) return;
        change(comps, comps - 1);
        if(s[x] < s[y]) swap(x, y);
        change(p[y], x);
        change(s[x], s[x] + s[y]);    
    }

    DSU(int n = 0)
    {
        this->n = n;
        s = vector<int>(n, 1);
        p = vector<int>(n);
        iota(p.begin(), p.end(), 0);
        comps = n;
    }
};

struct edge
{
    char g;
    int x;
    int y;
    edge(char g = 'A', int x = 0, int y = 0) : g(g), x(x), y(y) {};
};

DSU A, united;
vector<edge> T[4 * N];
int ans[N];

void dfs(int v, int l, int r)
{
    int state = cur;
    for(auto e : T[v])
    {
        united.merge(e.x, e.y);
        if(e.g == 'A') A.merge(e.x, e.y);   
    }
    if(l == r - 1)
    {
        ans[l] = A.comps - united.comps;
    }
    else
    {
        int m = (l + r) / 2;
        dfs(v * 2 + 1, l, m);
        dfs(v * 2 + 2, m, r);
    }
    while(state != cur) rollback();
}

void add_edge(int v, int l, int r, int L, int R, edge e)
{
    if(L >= R) return;
    if(L == l && R == r) T[v].push_back(e);
    else
    {
        int m = (l + r) / 2;
        add_edge(v * 2 + 1, l, m, L, min(m, R), e);
        add_edge(v * 2 + 2, m, r, max(L, m), R, e);
    }
}

map<pair<int, int>, int> last[2];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    A = DSU(n);
    united = DSU(n);
    for(int i = 0; i < q; i++)
    {
        string s;
        int x, y;
        cin >> s >> x >> y;
        --x;
        --y;
        int idx = (s[0] == 'A' ? 0 : 1);
        if(x > y) swap(x, y);
        if(last[idx].count(make_pair(x, y)) == 0)
        {
            last[idx][make_pair(x, y)] = i;
        }
        else
        {
            add_edge(0, 0, q, last[idx][make_pair(x, y)], i, edge(s[0], x, y));
            last[idx].erase(make_pair(x, y));
        }
    }
    for(int i = 0; i < 2; i++)
        for(auto a : last[i])
            add_edge(0, 0, q, a.second, q, edge(char(i + 'A'), a.first.first, a.first.second));
    dfs(0, 0, q);
    for(int i = 0; i < q; i++)
        cout << ans[i] << "\n";
}