#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxl=10001;
const int maxn=8200;
struct Pla{
	char str[maxl];
	bool ope[maxn];
	int N,step,l;
	int dp(int i,int out){
		if(i*2>N){
			if(ope[i]==0&&out==1)return 1;
			if(ope[i]==1&&out==1)return 2;
			return 0;
		}
		if(out!=1)return 0;
		else if(ope[i]==1)return dp(i<<1,1)+dp(i<<1|1,1);
		else return min(dp(i<<1,1)+dp(i<<1|1,0),dp(i<<1,0)+dp(i<<1|1,1));
	}
	void init(){
		scanf("%d",&N);N--;
		scanf("%s",str);
		for(int i=1;i<=N;i++)scanf("%d",&ope[i]);
		step=dp(1,1);l=strlen(str);
	}
	void work(){
		int ret=0,now=0;
		for(int i=0;i<l;i++)
			if(str[i]-'0'!=now){
				now=str[i]-'0';
				ret++;
			}
		if(ret)ret+=step;
		printf("%d\n",ret-1);
	}
}sol;
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		sol.init();
		sol.work();
	}
	return 0;
}