Problem AH
Cousins

Two strings $a$ and $b$ are defined to be first cousins if they can be made equal by removing no more than half the characters from each. For example, “abcdef” and “axcyd” are first cousins because we can remove $3$ of the $6$ characters (b, e, and f) from the first string and $2$ of the $5$ characters in the second string (x and y) resulting in “acd”. Two strings $c$ and $d$ are said to be $(n+1)$:st cousins if there exists a string $e$ that is a first cousin of $c$ and is an $n$:th cousin of $d$.

Given two strings $x$ and $y$, determine the smallest $n \ge 1$ such that $x$ is an $n$:th cousin of $y$.

Input

The input consists of several test cases. Each test case consists of two lines representing $x$ and $y$. $x$ and $y$ each consist of at least $1$ and at most $100$ lower case letters.

Two lines containing 0 follows the last test case.

There will be at most 15 test cases in a single input.

Output

For each test case, output a line containing $n$ or not related if $x$ and $y$ are not $n$:th cousins for any $n$.

a
b
abb
baa
abcdef
axcyd
0
0

2
2
1