#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,q;
string s1, s2;
int a[200005];
int b[200005];
int p1[200005];
int p2[200005];
int segp[400005];
int segs[400005];
int fpsum[50];
int brrp[55];
int brrs[55];
int lis[15];
void buildp(){
for(int i=n-1; i>=1; i--){
segp[i] = segp[2*i] + segp[2*i+1];
}
return;
}
void builds(){
for(int i=n-1; i>=1; i--){
segs[i] = segs[2*i] + segs[2*i+1];
}
return;
}
void updp(int pos, int val){
pos += n-1;
segp[pos] = val;
for(int i=pos/2; i>=1; i/=2){
segp[i] = segp[2*i] + segp[2*i+1];
}
}
void upds(int pos, int val){
pos += n-1;
segs[pos] = val;
for(int i=pos/2; i>=1; i/=2){
segs[i] = segs[2*i] + segs[2*i+1];
}
}
int qrp(int l, int r){
l+=n-1;
r+=n-1;
int sm = 0;
while(l<=r){
if(l%2==1){
sm += segp[l];
l++;
}
if(r%2==0){
sm += segp[r];
r--;
}
l/=2;
r/=2;
}
return sm;
}
int qrs(int l, int r){
l+=n-1;
r+=n-1;
int sm = 0;
while(l<=r){
if(l%2==1){
sm += segs[l];
l++;
}
if(r%2==0){
sm += segs[r];
r--;
}
l/=2;
r/=2;
}
return sm;
}
signed main(){
int t;
int cn1;
int cn2;
int mn;
cin>>t;
while(t--){
cin>>n;
for(int i=0; i<=14; i++){
lis[i] = 0;
}
cin>>q;
cin>>s1>>s2;
mn = 1e15;
cn1 = 0;
cn2 = 0;
for(int i=1; i<=n; i++){
if(s1[i-1]=='1'){
cn1++;
a[cn1] = i;
}
}
for(int i=1; i<=n; i++){
if(s2[n-i]=='1'){
cn2++;
b[cn2] = i;
}
}
p1[0] = 0;
p2[0] = 0;
for(int i=1; i<=cn1; i++){
p1[i] = p1[i-1] + a[i];
}
for(int i=1; i<=cn2; i++){
p2[i] = p2[i-1] + b[i];
}
if(cn1+cn2<=n){
cout<<-1<<endl;
}
else {
for(int i=n+1-cn2; i<=cn1; i++){
mn = min(mn, p1[i] + p2[n+1-i] - (i)*(i+1)/2 - (n+1-i)*(n+2-i)/2);
}
cout<<mn<<endl;
}
for(int i=0; i<n; i++){
if(s1[i]=='0'){
segp[n+i] = 0;
segs[n+i] = 0;
}
else {
segp[n+i] = 1;
segs[n+i] = i+1;
}
}
int cur = 0;
for(int i=1; i<=n; i++){
if(s2[n-i]=='1'){
cur++;
lis[cur] = i;
}
}
buildp();
builds();
while(q--){
int n1, n2;
cin>>n1>>n2;
mn = 1e15;
if(n1==2){
if(s2[n2-1]=='0'){
s2[n2-1]='1';
cn2++;
int com = 0;
for(int i=1; i<cn2; i++){
if(lis[i]<n+1-n2){
com++;
}
}
for(int i=cn2+1; i>=com+2; i--){
lis[i] = lis[i-1];
}
lis[com+1] = n+1-n2;
}
else {
s2[n2-1] = '0';
cn2--;
int com = 0;
for(int i=1; i<=cn2+1; i++){
if(lis[i] == n+1-n2){
com = i;
}
}
for(int i=com; i<=cn2; i++){
lis[i] = lis[i+1];
}
lis[cn2+1] = 0;
}
}
else {
if(s1[n2-1]=='0'){
s1[n2-1]='1';
updp(n2, 1);
upds(n2, n2);
cn1++;
}
else {
s1[n2-1] = '0';
updp(n2, 0);
upds(n2, 0);
cn1--;
}
}
if(cn1+cn2<=n){cout<<-1<<endl;}
else {
for(int i=1; i<=20; i++){
brrs[i] = 1e15;
}
int suu[25];
suu[1] = qrs(1, n);
for(int i=2; i<=cn2; i++){
suu[i] = suu[i-1] - segs[2*n+2-i];
}
brrp[1] = qrp(1,n);
for(int i=2; i<=cn2; i++){
brrp[i] = brrp[i-1] - segp[2*n+1-i];
}
for(int i=1; i<=cn2; i++){
brrs[n+1-brrp[i]] = suu[i];
}
fpsum[0] = 0;
for(int i=1; i<=cn2; i++){
fpsum[i] = fpsum[i-1] + lis[i];
}
for(int i=n+1-cn1; i<=cn2; i++){
mn = min(mn, fpsum[i] + brrs[i] - i*(i+1)/2 - (n+1-i)*(n+2-i)/2);
}
cout<<mn<<endl;
}
}
}
return 0;
}
