Internet Problem Solving Contest

• Easy input data set – A1
• Hard input data set – A2

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.

Problem specification

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

Input specification

The first line of the input file contains an integer t specifying the number of test cases. (In the easy subproblem A1 we have t = 10, in the hard subproblem A2 we have 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 specification

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.

Example

Input:

3

superfastawesome
superfastaxesome

superfastawesome
xuper

superfastawesome
superfastawe

Output:

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

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