#include#include #include #include #include #include #include #include using namespace std; int num,v[10005]; struct node { int num; int step; }; void bfs(int t) { int a[5]; queue q; node s,temp; s.num = t; s.step = 0; q.push(s); while(!q.empty()) { temp = q.front(); q.pop(); a[0] = temp.num/1000; a[1] = (temp.num/100)%10; a[2] = (temp.num/10)%10; a[3] = temp.num%10; //交换千位和百位 s.num = a[1]*1000 + a[0]*100 + a[2]*10 + a[3]; s.step = temp.step + 1; if(s.num == num) {printf("%d\n",s.step); return ;} if(!v[s.num]) {v[s.num] = 1; q.push(s);} //交换百位和十位 s.num = a[0]*1000 + a[2]*100 + a[1]*10 + a[3]; s.step = temp.step + 1; if(s.num == num) {printf("%d\n",s.step); return ;} if(!v[s.num]) {v[s.num] = 1; q.push(s);} //交换十位和个位 s.num = a[0]*1000 + a[1]*100+ a[3]*10 + a[2]; s.step = temp.step + 1; if(s.num == num) {printf("%d\n",s.step); return ;} if(!v[s.num]) {v[s.num] = 1; q.push(s);} for(int i = 0; i < 4; i ++) { int k = a[i]; //加一 if(a[i] == 9) {a[i] = 1; s.num = a[0]*1000 + a[1]*100 + a[2]*10 + a[3];} else {a[i] ++; s.num = a[0]*1000 + a[1]*100 + a[2]*10 + a[3];} s.step = temp.step + 1; if(s.num == num) {printf("%d\n",s.step);return ;} if(!v[s.num]) {v[s.num] = 1;q.push(s);} a[i] = k; //减一 if(a[i] == 1) {a[i] = 9; s.num = a[0]*1000 + a[1]*100 + a[2]*10 + a[3];} else {a[i] --; s.num = a[0]*1000 + a[1]*100 + a[2]*10 + a[3];} s.step = temp.step + 1; if(s.num == num) {printf("%d\n",s.step);return ;} if(!v[s.num]) {v[s.num] = 1;q.push(s);} a[i] = k; } } } int main() { int T,t; scanf("%d",&T); while(T--) { scanf("%d%d",&t,&num); memset(v,0,sizeof(v)); bfs(t); } return 0; }