#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}

int t;
int f[1000005],cnt[1000005];
char s[1000005];

void solve() {
	int n,ans=0;
	memset(f,0,sizeof(f));
	n=read();
	for(int i=1;i<=n;i++) cnt[i]=2147483646;
	scanf("%s",s+1);
	for(int i=1;i<=n;i++) {
		if(s[i]=='0') f[i]=0;
		else f[i]=1;
	}
	for(int i=1;i<=n;i++) {
		for(int j=i;j<=n;j+=i) {
			if(f[j]==1) break;
			cnt[j]=min(cnt[j],i);
		}
	}
	for(int i=1;i<=n;i++) {
		if(f[i]==0) ans+=cnt[i];
	}
	cout<<ans<<endl;
}

int main() {
	t=read();
	while(t--) {
		solve();
	}
	return 0;
}