#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
unordered_map<string,int> vis;
string s,f;
int n;
cin>>s>>f;
n=s.length();
int pos = 0;
for(int i = 0 ; i<s.length(); i++){
if(s[i]=='_'){
pos = i;
break;
}
}
queue<pair<string,int> > q;
q.push({s,pos});
vis[s]=0;
while(!q.empty()){
string ss = q.front().first;
int pp = q.front().second;
int dist = vis[ss];
q.pop();
if(pp>0){
swap(ss[pp],ss[pp-1]);
if(!vis.count(ss)){
if(ss==f){
cout<<dist+1<<"\n";
break;
}
vis[ss]=dist+1;
q.push({ss,pp-1});
}
swap(ss[pp],ss[pp-1]);
}
if(pp<n-1){
swap(ss[pp],ss[pp+1]);
if(!vis.count(ss)){
if(ss==f){
cout<<dist+1<<"\n";
break;
}
vis[ss]=dist+1;
q.push({ss,pp+1});
}
swap(ss[pp],ss[pp+1]);
}
if(pp>1 && ss[pp-1]!=ss[pp-2]){
swap(ss[pp],ss[pp-2]);
if(!vis.count(ss)){
if(ss==f){
cout<<dist+1<<"\n";
break;
}
vis[ss]=dist+1;
q.push({ss,pp-2});
}
swap(ss[pp],ss[pp-2]);
}
if(pp<n-2 && ss[pp+1]!=ss[pp+2]){
swap(ss[pp],ss[pp+2]);
if(!vis.count(ss)){
if(ss==f){
cout<<dist+1<<"\n";
break;
}
vis[ss]=dist+1;
q.push({ss,pp+2});
}
swap(ss[pp],ss[pp+2]);
}
}
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCBtYWluKCkgewoJaW50IHQ7CgljaW4+PnQ7Cgl3aGlsZSh0LS0pewoJCXVub3JkZXJlZF9tYXA8c3RyaW5nLGludD4gdmlzOwoJCXN0cmluZyBzLGY7CgkJaW50IG47CgkJY2luPj5zPj5mOwoJCW49cy5sZW5ndGgoKTsKCQlpbnQgcG9zID0gMDsKCQlmb3IoaW50IGkgPSAwIDsgaTxzLmxlbmd0aCgpOyBpKyspewoJCQlpZihzW2ldPT0nXycpewoJCQkJcG9zID0gaTsKCQkJCWJyZWFrOwoJCQl9CgkJfQoJCXF1ZXVlPHBhaXI8c3RyaW5nLGludD4gPiBxOwoJCXEucHVzaCh7cyxwb3N9KTsKCQl2aXNbc109MDsKCQl3aGlsZSghcS5lbXB0eSgpKXsKCQkJc3RyaW5nIHNzID0gcS5mcm9udCgpLmZpcnN0OwoJCQlpbnQgcHAgPSBxLmZyb250KCkuc2Vjb25kOwoJCQlpbnQgZGlzdCA9IHZpc1tzc107CgkJCXEucG9wKCk7CgkJCWlmKHBwPjApewoJCQkJc3dhcChzc1twcF0sc3NbcHAtMV0pOwoJCQkJaWYoIXZpcy5jb3VudChzcykpewoJCQkJCWlmKHNzPT1mKXsKCQkJCQkJY291dDw8ZGlzdCsxPDwiXG4iOwoJCQkJCQlicmVhazsKCQkJCQl9CgkJCQkJdmlzW3NzXT1kaXN0KzE7CgkJCQkJcS5wdXNoKHtzcyxwcC0xfSk7CgkJCQl9CgkJCQlzd2FwKHNzW3BwXSxzc1twcC0xXSk7CgkJCX0KCQkJaWYocHA8bi0xKXsKCQkJCXN3YXAoc3NbcHBdLHNzW3BwKzFdKTsKCQkJCWlmKCF2aXMuY291bnQoc3MpKXsKCQkJCQlpZihzcz09Zil7CgkJCQkJCWNvdXQ8PGRpc3QrMTw8IlxuIjsKCQkJCQkJYnJlYWs7CgkJCQkJfQoJCQkJCXZpc1tzc109ZGlzdCsxOwoJCQkJCXEucHVzaCh7c3MscHArMX0pOwoJCQkJfQoJCQkJc3dhcChzc1twcF0sc3NbcHArMV0pOwoJCQl9CgkJCWlmKHBwPjEgJiYgc3NbcHAtMV0hPXNzW3BwLTJdKXsKCQkJCXN3YXAoc3NbcHBdLHNzW3BwLTJdKTsKCQkJCWlmKCF2aXMuY291bnQoc3MpKXsKCQkJCQlpZihzcz09Zil7CgkJCQkJCWNvdXQ8PGRpc3QrMTw8IlxuIjsKCQkJCQkJYnJlYWs7CgkJCQkJfQoJCQkJCXZpc1tzc109ZGlzdCsxOwoJCQkJCXEucHVzaCh7c3MscHAtMn0pOwoJCQkJfQoJCQkJc3dhcChzc1twcF0sc3NbcHAtMl0pOwoJCQl9CgkJCWlmKHBwPG4tMiAmJiBzc1twcCsxXSE9c3NbcHArMl0pewoJCQkJc3dhcChzc1twcF0sc3NbcHArMl0pOwoJCQkJaWYoIXZpcy5jb3VudChzcykpewoJCQkJCWlmKHNzPT1mKXsKCQkJCQkJY291dDw8ZGlzdCsxPDwiXG4iOwoJCQkJCQlicmVhazsKCQkJCQl9CgkJCQkJdmlzW3NzXT1kaXN0KzE7CgkJCQkJcS5wdXNoKHtzcyxwcCsyfSk7CgkJCQl9CgkJCQlzd2FwKHNzW3BwXSxzc1twcCsyXSk7CgkJCX0KCQl9Cgl9CglyZXR1cm4gMDsKfQ==