Wildcard (Large)

Many operating systems let you use * (an asterisk) as a wildcard when you name a file. A * matches any string, and the empty string counts.

Wildcards are often used to name several files at once, and they also make naming a single file easier. Suppose you want to name the file pascalisamazing. If it is the only file matching the pattern pascal*, then that pattern names pascalisamazing, and pascal* is much shorter to type.

Given two file names, find the shortest pattern that matches the first name but not the second.

A pattern is a string of lowercase letters and *. The pattern matches a name if you can replace each * in it with some string, possibly the empty string, and get exactly that name.

The first line has the number of test cases $T$. Each test case takes two lines: the first file name $A$ on one line and the second file name $B$ on the next. File names consist of lowercase letters only.

Constraints

• $1 \le T \le 100$
• $A$ and $B$ are different strings
• $A$ and $B$ are each 1 to 50 characters long

For each test case print one line in this format.

Case #X: Y

$X$ is the test case number and $Y$ is the shortest pattern that matches $A$ but not $B$. If several patterns share the shortest length, print the one with the fewest asterisks. If several still remain, print the smallest one in lexicographic order. Compare characters by their ASCII codes, where the code 42 of * is smaller than any lowercase letter.