INVESORT - Inversion Sort

You have just bought an old fashioned jukebox that can hold 10 music albums. Albums are maintained as a sequence, each album represented by a unique lowercase letter between “a” and “j”, inclusive. The jukebox allows you to select a subsequence of contiguous albums and a mechanical arm inverts that part of the sequence. For instance, if the current sequence is “abcdefghij” and you select the subsequence “bcd”, the result of the inversion would be “adcbefghij”. Soon you notice that it is possible to get the albums into any desired order using simply inversions. However, you are interested in doing so with the minimum number of operations. Given the current order and a desired order of the 10 music albums, find the minimum number of inversion operations needed to obtain the desired order.

Input

The input contains several test cases, each one described in a single line. The line contains two strings C and D separated by a single space, representing the current and desired orders of the music albums, respectively. Each of the strings has exactly 10 characters and contains the characters of “abcdefghij” in some order. The last line of the input contains two asterisks (“*”) separated by a single space and should not be processed as a test case.

Output

For each test case output a single line with an integer representing the minimum number of inversions needed to transform the current order given by C, into the desired order given by D.

Example

Input:
abcdefghij adcbefghij
abcdefghij abcdefghij
bcdaefghji beagfcdhji
* *

Output:
1
0
2

Added by:Pablo Ariel Heiber
Date:2010-08-24
Time limit:89.26s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET
Resource:FCEyN UBA ICPC Selection 2009

hide comments
2023-12-30 09:18:34
this problem is of which topic ?
2023-12-14 18:27:50
taci mihnea
2023-12-14 18:01:24
Bruh moment
2023-12-14 17:45:54
it is a great problem!
2021-11-11 18:06:41
what willbe the ans of this case:
abcdefghij jcfghiadeb
* *
2021-04-03 13:56:56
Meet in the middle will work
2021-04-02 19:28:34
wow

Last edit: 2021-04-02 19:29:10
2021-02-08 19:01:51
where can i find editorial for this problem ??
2019-05-05 13:18:02
Please give some hints on this problem. Shall we use graph bfs search to solve this. Please guide me I am a newbie
2016-05-26 19:25:27
can some one give me some case ??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.