#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
int mod = 1e9 + 7;
const int N = 100010;
const int M = 1000010;
int tr[5010], n;
int lowbit(int x)
{
    return x&-x;
}

int fd(int x)
{
    int sum=0;
    for(int i=x;i;i-=lowbit(i))
    {
        sum+=tr[i];
    }
    return sum;
}
void add(int x,int v)
{
    for(int i=x;i<=n;i+=lowbit(i))
    {
        tr[i]+=v;
    }
}
void solve()
{
    string a;
    cin >> n >> a;
    a=" "+a;
    for (int k=n;k>0;k--)
    {
        for (int j = 1; j <= n; j++)
            tr[j] = 0;
        int z = 1;
        for (int j = 1; j <= n; j++)
        {
            int u = fd(j);//当前位置的操作次数 
            if ((u + a[j] - '0') % 2 == 0)//0 操作数为偶数  1 操作数为奇数  两种情况需要操作 
            {
                if (j+k-1 > n )//如果k不够了 
                {
                    z = 0;
                    break;
                }
                add(j, 1);//区间 (j,j+k-1)操作 树状数组差分 区间修改 
                if (j + k <= n)
                    add(j + k, -1);//l +=1 r+1 -=1
            }
        }
        if (z)
        {
            cout << k<< endl;
            return;
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}