#include <bits/stdc++.h> using namespace std; using ll = long long; using pll = pair<ll, ll>; #define drep(i, cc, n) for (ll i = (cc); i <= (n); ++i) #define rep(i, n) drep(i, 0, n - 1) #define all(a) (a).begin(), (a).end() #define pb push_back #define fi first #define se second const ll MOD = 1000000007; const ll MOD2 = 998244353; const ll INF = 1LL << 60; const ll MAX_N = 2e5; void solve(){ ll n; cin >> n; string s; cin >> s; //初期化 bool ok = false; if(s[0]=='?' && s[1]=='?'){ rep(a, 2) rep(b, 2){ string t=""; t+=(char)('0'+a); t+=(char)('0'+b); for(ll i=2; i<n; i++) t+=s[i]; t+=(char)('0'+a); t+=(char)('0'+b); vector<vector<bool>> dp(n+2, vector<bool>(4, false)); dp[1][2*a+b]=true; for(ll i=2; i<n+2; i++){ if(t[i]=='0' || t[i]=='?'){ //0とする for(ll j=1; j<4; j++){ dp[i][(j%2)*2] = dp[i][(j%2)*2] | dp[i-1][j]; } } if(t[i]=='1' || t[i]=='?'){ //1とする for(ll j=0; j<3; j++){ dp[i][(j%2)*2+1] = dp[i][(j%2)*2+1] | dp[i-1][j]; } } } rep(j, 4) ok = ok | dp[n+1][j]; } }else if(s[0]=='?'){ rep(a, 2){ string t=""; t+=(char)('0'+a); t+=s[1]; for(ll i=2; i<n; i++) t+=s[i]; t+=(char)('0'+a); t+=s[1]; vector<vector<bool>> dp(n+2, vector<bool>(4, false)); dp[1][2*a+(s[1]=='1')]=true; for(ll i=2; i<n+2; i++){ if(t[i]=='0' || t[i]=='?'){ //0とする for(ll j=1; j<4; j++){ dp[i][(j%2)*2] = dp[i][(j%2)*2] | dp[i-1][j]; } } if(t[i]=='1' || t[i]=='?'){ //1とする for(ll j=0; j<3; j++){ dp[i][(j%2)*2+1] = dp[i][(j%2)*2+1] | dp[i-1][j]; } } } rep(j, 4) ok = ok | dp[n+1][j]; } }else if(s[1]=='?'){ rep(b, 2){ string t=""; t+=s[0]; t+=(char)('0'+b); for(ll i=2; i<n; i++) t+=s[i]; t+=s[0]; t+=(char)('0'+b); vector<vector<bool>> dp(n+2, vector<bool>(4, false)); dp[1][2*(s[0]=='1')+b]=true; for(ll i=2; i<n+2; i++){ if(t[i]=='0' || t[i]=='?'){ //0とする for(ll j=1; j<4; j++){ dp[i][(j%2)*2] = dp[i][(j%2)*2] | dp[i-1][j]; } } if(t[i]=='1' || t[i]=='?'){ //1とする for(ll j=0; j<3; j++){ dp[i][(j%2)*2+1] = dp[i][(j%2)*2+1] | dp[i-1][j]; } } } rep(j, 4) ok = ok | dp[n+1][j]; } }else{ string t=""; t+=s[0]; t+=s[1]; for(ll i=2; i<n; i++) t+=s[i]; t+=s[0]; t+=s[1]; vector<vector<bool>> dp(n+2, vector<bool>(4, false)); dp[1][2*(s[0]=='1')+(s[1]=='1')]=true; for(ll i=2; i<n+2; i++){ if(t[i]=='0' || t[i]=='?'){ //0とする for(ll j=1; j<4; j++){ dp[i][(j%2)*2] = dp[i][(j%2)*2] | dp[i-1][j]; } } if(t[i]=='1' || t[i]=='?'){ //1とする for(ll j=0; j<3; j++){ dp[i][(j%2)*2+1] = dp[i][(j%2)*2+1] | dp[i-1][j]; } } } rep(j, 4) ok = ok | dp[n+1][j]; } if(ok) cout << "Yes" << '\n'; else cout << "No" << '\n'; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); ll t; cin >> t; rep(i, t) solve(); }