Cousin Strings

Two strings $a$ and $b$ are called first cousins if they can be made equal by deleting at most half of the characters from each string. For example, abcdef and axcyd are first cousins: deleting $3$ of the $6$ characters (b, e, f) from the first string and $2$ of the $5$ characters (x, y) from the second string leaves acd in both cases.

Two strings $c$ and $d$ are called $(n{+}1)$-th cousins if there exists a string $e$ that is a first cousin of $c$ and an $n$-th cousin of $d$.

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

The input contains several test cases. Each test case consists of two lines: the string $x$ on the first line and the string $y$ on the second line. Each of $x$ and $y$ contains between $1$ and $100$ lowercase letters. The input ends with a test case whose two lines each contain a single 0; this terminating case must not be processed.

For each test case, print a single line containing the smallest $n$ for which $x$ is an $n$-th cousin of $y$, or not related if no such $n$ exists.