#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;

int P[3630000], cp;
char D[3630000];

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);
}

int bsearch(int perm){
    int l = 0, r = cp;

    while(r-l > 1){
        int m = (l+r)/2;

        if(P[m] > perm) r = m; else l = m;
    }

    return l;
}

void calc(){
    queue< pair<int, int> > Q;
    Q.push(make_pair(0, 123456789));

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

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

        if(d > 10) return;
        if(D[ bsearch(perm) ] != -1) continue;
        D[ bsearch(perm) ] = d;

        forn(i, 10)
            forsn(j, i+1, 10)
                Q.push(make_pair(d+1, flip(perm, i, j)));

        }
}

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[ bsearch(n) ], pm = D[ bsearch(m) ];
        printf("%d\n", max(pn, pm)-min(pn, pm));
    }

    return 0;
}