rt,只会80pts

#include<bits/stdc++.h>
using namespace std;
#define nor unsigned long long
const int bit = 3;
char ch[2048];
int n;
nor H[2048],sum[2048],ksm[2048],TT;
bool chk(int l1,int r1,int l2,int r2) {
	for(int i1 = l1,i2 = l2;i1 <= r1 && i2 <= r2;++i1,++i2) if(!(ch[i1] == ch[i2] || ch[i1] == '?' || ch[i2] == '?')) return 0;
	return 1; 
}
void solve() {
	int ans = 0;
	cin >> n;
	int fg = 0;
	for(int i = 1;i <= n;++i) cin >> ch[i],fg += ch[i] == '?';
	for(int i = 1;i <= n;++i) H[i] = rand();
	if(!fg){
		ksm[0] = 1;
		for(int i = 1;i <= n;++i) sum[i] = (sum[i - 1] * bit + (ch[i] - '0')),ksm[i] = (ksm[i - 1] * bit);
		for(int l = 1;l <= n;++l) {
			for(int r = l + 1;r <= n;r += 2) {
				int mid = l + r >> 1;
				if(sum[mid] - sum[l - 1] * ksm[r - mid] == sum[r] - sum[mid] * ksm[r - mid]) ans = max(ans,r - l + 1);
			}
		}
		return cout << ans / 2 << '\n',void();
	}
	for(int l = 1;l <= n;++l) {
		for(int r = ans + l - 1;r <= n;r += 2) {
			if(r - l + 1 <= ans) continue;
			int mid = l + r >> 1;
			if(chk(l,mid,mid + 1,r)) ans = max(ans,r - l + 1);
		}
	}
	return cout << ans / 2 << '\n',void();
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin >> T;
	TT = T;
	while(T-->0)solve();
}