#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second

int bfs(string s, string t)
{
    if(s == t)
        return 0;
    queue<pair<string, int> > q;
    map<string, bool> mp;

    q.push({s, 0});
    mp[s] = 1;

    string p, temp;
    int x;
    while(!q.empty())
    {
        p = q.front().ff;
        x = q.front().ss;
        q.pop();
        for(int i = 0; i < p.size(); i++)
        {
            for(int j = i+1; j <= p.size(); j++)
            {
                temp = p;
                reverse(temp.begin() + i, temp.begin() + j);
                if(mp[temp])
                    continue;
                if(temp == t)
                    return x+1;
                mp[temp] = 1;
                q.push({temp, x+1});
            }
        }
    }
}

int main()
{
    string s, t;
    while(1)
    {
        cin >> s >> t;
        if(s == "*" && t == "*")
            break;
        cout << bfs(s, t) << endl;
    }
}