#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; typedef modint998244353 mint; typedef long long ll; void solve(){ int n; cin >> n; string s; cin >> s; vector<int> a(n); for (int i=0; i<n; i++){ if (s[i] == '0') a[i] = 0; if (s[i] == '1') a[i] = 1; if (s[i] == '?') a[i] = 2; } // first prefix 3 for (int num=1; num<7; num++){ bool mode = true; for (int j=0; j<3; j++){ if (num>>j&1){ if (a[j] == 0) mode = false; }else{ if (a[j] == 1) mode = false; } } if (!mode) continue; vector<bool> dp(8); dp[num] = true; for (int i=3; i<n; i++){ vector<bool> ndp(8); for (int j=0; j<8; j++){ if (!dp[j]) continue; int v = j>>1; if (a[i] == 0){ if (v != 0) ndp[v] = true; } else if (a[i] == 1){ if (v != 3) ndp[v+4] = true; }else{ if (v != 0) ndp[v] = true; if (v != 3) ndp[v+4] = true; } } dp = ndp; } for (int x=1; x<7; x++){ if (dp[x]){ bool mode = true; if ((x>>2&1)==(num>>0&1) && (num>>0&1)==(num>>1&1)) mode = false; if ((x>>1&1)==(x>>2&1) && (x>>2&1)==(num>>0&1)) mode = false; if (mode){ cout << "Yes\n"; return; } } } } cout << "No\n"; return; } int main(){ int t; cin >> t; while(t--) solve(); }