#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=;

int q[N],head[N],tot,S,T,dis[N];

struct node{

    int to,next,w;

}e[N<<];

void add(int u,int v,int w){

    e[tot].to=v;e[tot].next=head[u];e[tot].w=w;head[u]=tot++;

    e[tot].to=u;e[tot].next=head[v];e[tot].w=;head[v]=tot++;

}

bool bfs(){

    int l=,r=;

    q[r++]=S;

    memset(dis,-,sizeof(dis));

    dis[S]=;

    while(l<r) {

        int u=q[l++];

        for(int i=head[u];~i;i=e[i].next){

            int v=e[i].to;

            if(dis[v]==-&&e[i].w>) {

                dis[v]=dis[u]+;

                q[r++]=v;

                if(v==T) return true;

            }

        }

    }

    return false;

}

int dfs(int s,int low){

    if(!low||s==T) return low;

    int ans=low,a;

    for(int i=head[s];~i;i=e[i].next){

        int v=e[i].to;

        if(e[i].w>&&dis[v]==dis[s]+&&(a=dfs(v,min(ans,e[i].w)))) {

            ans-=a;

            e[i].w-=a;

            e[i^].w+=a;

            if(!ans) return low;

        }

    }

    if(low==ans) dis[s]=-;

    return low-ans;

}

int vis[<<],mark[],lim[],p[];

void init(){

    int cont=;

    for(int i=;i<;++i) {

        int S=;

        for(int j=;j<=;++j)  if(i%j==) S|=<<j;

        if(!vis[S]) vis[S]=++cont,p[cont]=S;

        mark[i]=vis[S];

    }

}

int main(){

    init();

    int Ta,n,x;

    for(scanf("%d",&Ta);Ta--;){

        tot=;

        memset(head,-,sizeof(head));

        memset(lim,,sizeof(lim));

        scanf("%d",&n);

        S=,T=;

        for(int i=;i<;++i) {

            int now=n/;

            if(i&&n%>=i) ++now;

            lim[mark[i]]+=now;

        }

        for(int i=;i<=;++i) add(i+,T,lim[i]);

        for(int i=;i<=;++i) {

            scanf("%d",&x);

            if(x) {

                add(S,i,x);

                for(int j=;j<=;++j) if(p[j]&(<<i)) add(i,j+,x);

            }

        }

        int ans=;

        while(bfs()) ans+=dfs(S,1e9+);

        printf("%d\n",ans);

    }

}