#include <bits/stdc++.h>
using namespace std;
int t, n, ans;
int f[1000005];
char ch[1000005];
void f__k(int x, int k) {
    //vector<int> v;
    for (int i = 1; i * i <= x; i++) {
        if (x % i == 0) {
            //v.push_back(i);
            f[i] = k;
            f[x / i] = k;
        }
    }
    
    return;
}
int check(int x, int k) {
    int sum = INT_MAX;
    for (int i = 1; i * i <= x; i++) {
        if (x % i == 0) {
            if (f[i] != k) {
                sum = min(sum, i);
            }
            if (f[x / i] != k) {
                sum = min(sum, x / i);
            }
        }
    }
    return sum;
}
int main() {
    cin >> t;
    for (int us = 1; us <= t; us++) {
        cin >> n;
        ans = 0;
        for (int i = 1; i <= n; i++) {
            cin >> ch[i];
            if (ch[i] == '1') {
                f__k(i, us);
            }else {
                ans = ans + check(i, us);
            }
        }
        cout << ans << "\n";
    }
    return 0;
}