#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int t;
cin>>t;
while(t--){
int n,k,c,d;
cin>>n>>k;
string a,b;
cin>>a>>b;
vector<int> ans(n+1);
ans[0]=0;
vector<int> v1(26,0),v2(26,0);
char c1,c2;
for(int i=0;i<n;++i){
c1=a[i]-'a';
c2=b[i]-'a';
v1[c1]++;
v2[c2]++;
if(c1==c2){
ans[i+1]=ans[i];
}
else if(v1[c1]==v2[c1] && v1[c2]==v2[c2]){
ans[i+1]=ans[i]-1;
}
else if(v1[c1]==v2[c1] || v1[c2]==v2[c2]){
ans[i+1]=ans[i];
}else{
ans[i+1]=ans[i]+1;
}
cout<<ans[i+1]<<" ";
}
for(int i=0;i<k;++i){
cin>>c>>d;
if(c==d) d=c-1;
cout<<abs(ans[c-1]-ans[d])<<endl;
}
}
return 0;
}
CgojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWFpbigpIHsKCS8vIHlvdXIgY29kZSBnb2VzIGhlcmUKCWludCB0OwoJY2luPj50OwoJd2hpbGUodC0tKXsKCQlpbnQgbixrLGMsZDsKCQljaW4+Pm4+Pms7CgkJc3RyaW5nIGEsYjsKCQljaW4+PmE+PmI7CgkJdmVjdG9yPGludD4gYW5zKG4rMSk7CgkJYW5zWzBdPTA7CgkJdmVjdG9yPGludD4gdjEoMjYsMCksdjIoMjYsMCk7CgkJY2hhciBjMSxjMjsKCQlmb3IoaW50IGk9MDtpPG47KytpKXsKCgkJCWMxPWFbaV0tJ2EnOwoJCQljMj1iW2ldLSdhJzsKCQkJdjFbYzFdKys7CgkJCXYyW2MyXSsrOwoJCQlpZihjMT09YzIpewoJCQkJYW5zW2krMV09YW5zW2ldOwoJCQl9CgkJCWVsc2UgaWYodjFbYzFdPT12MltjMV0gJiYgdjFbYzJdPT12MltjMl0pewoJCQkJYW5zW2krMV09YW5zW2ldLTE7CgkJCX0KCQkJZWxzZSBpZih2MVtjMV09PXYyW2MxXSB8fCB2MVtjMl09PXYyW2MyXSl7CgkJCQlhbnNbaSsxXT1hbnNbaV07CgkJCX1lbHNlewoJCQkJYW5zW2krMV09YW5zW2ldKzE7CgkJCX0KCQkJCgkJCWNvdXQ8PGFuc1tpKzFdPDwiICI7CgkJfQoJCWZvcihpbnQgaT0wO2k8azsrK2kpewoJCQljaW4+PmM+PmQ7CgkJCWlmKGM9PWQpIGQ9Yy0xOwoJCQljb3V0PDxhYnMoYW5zW2MtMV0tYW5zW2RdKTw8ZW5kbDsKCQl9CgkJCgkJCgkJCgkJCgl9CglyZXR1cm4gMDsKfQ==