#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

#define forn(i, n) for(int i = 0; i < (int) (n); i++)
#define forsn(i, s, n) for(int i = (s); i < (int) (n); i++)
#define dforn(i, n) for(int i = ((int)(n) -1 ); i >= 0; i--)

typedef pair<int, int> pint;

map<int, char> D;

void decode(int perm, int arr[]){
    forn(i, 10) arr[i] = i;

    bool app[10];
    memset(app, 0, sizeof(app));

    dforn(i, 9){
        arr[i] = perm % 10;
        app[ arr[i] ] = true;

        perm = perm/10;
    }

    forn(i, 10) if(!app[i]) arr[9] = i;
}

int encode(int arr[]){
    int perm = 0;
    forn(i, 9){
        perm = 10*perm + arr[i];
    }

    return perm;
}

int flip(int perm, int s, int e){
    int arr[10], arrcp[10]; decode(perm, arr);
    memcpy(arrcp, arr, sizeof(arr));

    forsn(i, s, e+1) arr[i] = arrcp[e+s-i];

    return encode(arr);
}

void calc(){
    queue< pair<int, int> > Q;

    int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    do{ D[ encode(arr) ] = -1; }while(next_permutation(arr, arr+10));

    D[12345678] = 0;
    Q.push(make_pair(0, 12345678));

    while(!Q.empty()){
        pint p = Q.front(); Q.pop();
        int perm = p.second, d = p.first;

        forn(i, 10)
            forsn(j, i+1, 10){
                int next = flip(perm, i, j);
                if(D[ next ] == -1 && d <= 10){
                    D[ next ] = d+1;
                    Q.push(make_pair(d+1, next));
                }
            }
    }
}

int main(){
#ifdef ACM
    freopen("test.in", "r", stdin);
#endif

    char s[16], t[16];

    calc();
    while(scanf("%s %s\n", s, t) && strcmp(s, "*")){
        int n = 0, m = 0;

        forn(i, 9){
            n = 10*n + (s[i] - 'a');
            m = 10*m + (t[i] - 'a');
        }

        int pn = D[ n ], pm = D[ m ];
        printf("%d\n", max(pn, pm)-min(pn, pm));
    }

    return 0;
}