#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t;
	cin>>t;
	for(int len=1;len<=t;len++){
		int n;
		string s;
		cin>>n>>s;
		int ans=0;
		for(int i=n;i>=2;i--){
			for(int j=0;j+i-1<n;j++){
				int l=j,r=j+i-1;
				bool flag=true;
				while(l<=r){
					if(s[l]!=s[r]){
						if(s[l]!='?'&&s[r]!='?'){
							flag=false;
							break;
						}
					}
					l++;
					r--;
			    }
				if(flag==true){
					ans=i;
					break;
				}
			}
			if(ans>0){
				cout<<ans/2<<"\n";
				break;
			}
		}
		//cout<<mx<<endl;
	}
	return 0;
}