Question Link
#include <iostream>
#include <iomanip>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <map>
#include <typeinfo>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <bitset>
#include <unordered_set>
#include <limits.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL)
#define vi vector <int>
#define fri(i,a,b) for(int i=a; i<b;i++ )
int main(){
FAST;
int t; cin >> t;
while(t--){
int n ; cin >> n ;
vector<char> v(n);
vector<char> p(n);
fri(i,0,n){
char c; cin >> c;
v[i]= c;
}
fri(i,0,n){
char c; cin >> c;
p[i]= c;
}
vi left(n,0);
vi stay(n,0);
vi right(n,0);
left[0]=0;
right[0]=0;
stay[0] = (p[0]=='1' && v[0]=='0');
if(v[1]=='1' && p[0]=='1'){
right[0]=1;
}
fri(i,1,n){
if(i==n-1){
right[i]=max(left[i-1],max(stay[i-1],right[i-1]));
left[i]=max(left[i-1],right[i-1])+(p[i]=='1' && v[i-1]=='1');
stay[i]=max(left[i-1],stay[i-1]) + (p[i]=='1' && v[i]=='0');
}
else{
right[i]=max(left[i-1],max(stay[i-1],right[i-1]))+(p[i]=='1' && v[i+1]=='1');
left[i]=max(left[i-1],right[i-1])+(p[i]=='1' && v[i-1]=='1');
stay[i]=max(left[i-1],stay[i-1]) + (p[i]=='1' && v[i]=='0');
}
}
cout << max(right[n-1],max(left[n-1],stay[n-1]))<<endl;
}
return 0;
}