#include<bits/stdc++.h>
using namespace std;
int t,n,a[100001];
string s;
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n>>s;
		int cnt=0;
		for(int i=0;i<s.size();i++)
		{
			if(s[i]!=s[i-1]) 
			{
				cnt++;
				a[cnt]=1;
			}
			else a[cnt]++;
		}
		bool p=true;
		for(int i=1;i<=cnt;i++)
		if(a[i]!=1) p=false;
		if(p)
		{
			cout<<0<<endl;
			continue;
		}
		int ansmax=0;
		for(int i=1;i<=cnt;i++)
		{
			if(a[i]>=2)
			 ansmax=max(ansmax,max(i,cnt-i+1));
		//	 cout<<a[i]<<" ";
		}
		int sum=0,ansmin=INT_MAX;
		for(int i=1;i<=cnt;i++)
		{
			if(a[i]==1) sum++;
			else sum=0;
			if(sum>cnt/2) ansmin=sum;
		}
		if(ansmin==INT_MAX) ansmin=cnt/2;
		ansmin++;
		cout<<ansmax-ansmin<<endl;
	}
	return 0;
}