E

#include <bits/stdc++.h>

using namespace std;

#define ll     long long
#define _test   int _TEST; cin>>_TEST; while(_TEST--)
#define pb     push_back
#define ppb    pop_back
#define pf     push_front
#define ppf    pop_front

int main()
{
    _test
    {
        int n;
        string s;
        cin>>n>>s;

        int ans = 1;

        vector<int> flip(n);

        for(int k=2; k<=n; k++)
        {
            fill(flip.begin(), flip.end(), 0);
            int f = 0;

            for(int i=0; i<=n-k; i++)
            {
                if((f+(s[i]-'0'))%2 == 0)
                {
                    f ^= 1;
                    flip[i+k-1] = 1;
                }

                f ^= flip[i];
            }

            int chk = 1;

            for(int i=n-k+1; i<n; i++)
            {
                chk &= ((f+(s[i]-'0'))%2 == 1);
                f ^= flip[i];
            }

            if(chk)     ans = k;
        }

        cout<<ans<<"\n";
    }
}