#include<bits/stdc++.h>
#include<vector>
#define maxn 1000005
using namespace std;
int t,n,m;
string s;
vector<int>vis[maxn];
vector<int>::iterator itc;
vector<int>::iterator res;
signed main()
{
	cin>>t;
	while(t--)
	{
		int ans=0;
		cin>>n>>s;
		for(int i=1;i<=n;i++) vis[i].clear();
		for(int i=0;i<s.size();i++)
		{
			if(s[i]=='0')
			{
				if(vis[i+1].size())
				{
					//cout<<vis[i+1]<<endl;
					int flag=1e9,pos=0;
					for(int k=0;k<vis[i+1].size();k++)
					{
						bool flg=1;
						for(int j=vis[i+1][k];j<=i;j+=vis[i+1][k])
						{
							res=find(vis[j].begin(),vis[j].end(),vis[i+1][k]);
							if(res!=vis[j].end())
							{
								flg=0;
								break;
							}
						}
						if(flg)
						{
							if(vis[i+1][k]<flag)
							{
								flag=vis[i+1][k];
							}
						}
					}
					if(flag!=1e9)
					{
						ans+=flag;
						if(find(vis[i+1].begin(),vis[i+1].end(),flag)!=vis[i+1].end())
						{
							//cout<<"qwq"<<endl;
							vis[i+1].erase(find(vis[i+1].begin(),vis[i+1].end(),flag));
						}
						/*itc=vis[i+1].begin();
                        while(itc!=vis[i+1].end())
                        {
                            if(*itc==flag) 
							{
								itc=vis[i+1].erase(itc);
								cout<<"qwq"<<endl;
							}
                            else itc++;
                        }*/
					}
					else
					{
						ans+=i+1;
						if(find(vis[i+1].begin(),vis[i+1].end(),i+1)!=vis[i+1].end()) vis[i+1].erase(find(vis[i+1].begin(),vis[i+1].end(),i+1));
					}
				}
                else ans+=i+1;
                for(int j=(i+1)*2;j<=n;j+=i+1)
			    {
				    vis[j].push_back(i+1);
			    }
			}
			//cout<<ans<<endl;
		}
		cout<<ans<<endl;
	}
	return 0;
}