Adjusting passwords

Interview

Time limit1sMemory limit1024 MB

Summary

Given the correct password P and the mistyped prompt text Q, find the fewest keystrokes (letters, backspace, enter) that log in.

Level: Easy3 of 10
Topics: String, Greedy
Solved: No attempts yet

Problem

Another IPSC has just started and you are late! You rush to your PC only to discover that you locked the screen and now you have to enter your password quickly to unlock it.

You are presented with a password prompt. It only supports the following keys:

Key	Action
`a` to `z`	enters the character.
enter	submits the password.
backspace	erases the last entered character, if any.

If you submit an invalid password, you will see an error message and a new, empty prompt will open.

Your password is P. In all the rush, you just typed the string Q into the prompt. It is possible that Q is not P: there may be a typo or two, or it can even be a completely different string.

Given P and Q, log in using as few additional keystrokes as possible.

Input

The first line of the input contains an integer t specifying the number of test cases. (t ≤ 1000) Each test case is preceded by a blank line.

Each test case consists of two lines. The first line contains the correct password P and the second line contains the already typed string Q. Both are non-empty and have at most 50 characters.

Output

For each test case, output a line containing the list of keystrokes you want to press. Pressing enter is represented by * and pressing backspace is represented by <.

If there are multiple optimal solutions, you may output any of them.

Hint

In the first test case, we keep pressing backspace until we delete the typo. In the second test case, it is faster to press enter immediately, receive an error message, and begin anew from an empty prompt.

Examples1

Example 1

Input

3

superfastawesome
superfastaxesome

superfastawesome
xuper

superfastawesome
superfastawe

Expected output

<<<<<<wesome*
*superfastawesome*
some*