Cloud Storage

Cloud storage is a new concept that extends and develops from the concept of cloud computing. Simply put, cloud storage is an emerging solution that places storage resources in the cloud for users to access. Users can connect to the cloud from any time, any place, and through any internet-connected device to conveniently access data.

JYY wants to study how to improve the data transmission efficiency of cloud storage. One interesting problem concerns the transmission of data modification information. JYY discovered that if a user needs to modify a file stored in the cloud, in many cases, only a small part of the file is changed, while most of the other content remains the same. In such cases, it is unnecessary to transmit the entire modified file over the network to the cloud to overwrite the previous file. If the modification information can be summarized before transmission, the efficiency will be greatly improved. For example, if a user performs a replacement operation on a document, they actually only need to transmit a command in the following format:

$s/\langle string \rangle/\langle replacement \rangle/g$

The meaning of this command is to replace all occurrences of the $\langle string \rangle$ field in the document with the $\langle replacement \rangle$ field.

A more precise definition of "replacement" is as follows: if a replacement command $s/A/B/g$ (where $A$ and $B$ are strings, and $A$ is non-empty) is executed on a string $S$, the following operations are performed:

(1) Start from the left end of $S$ to find the first occurrence of field $A$. If it cannot be found, the result is $S$; otherwise, $S$ can be split into $S_L+A+S_R$ (where $S_L$ does not contain field $A$);

(2) Execute the replacement command $s/A/B/g$ on $S_R$ to obtain $T_R$; then the result of the replacement on $S$ is $S_L+B+T_R$.

JYY wants to know, for a given initial string and a modified string, how to summarize the replacement command that was executed. If there are multiple feasible replacement commands, JYY wants to find the one with the shortest length.

Input

The input contains multiple test cases. The first line contains an integer $T$, representing the number of test cases.

Following this are $T$ test cases. Each test case consists of two lines, each containing a string. The first line is the initial string, and the second line is the modified string. It is guaranteed that the two strings are not identical. There are no empty lines between adjacent test cases.

The input strings only contain the following characters: uppercase and lowercase English letters, Arabic numerals, spaces, and 5 common punctuation marks (,, ., :, ;, -).

Output

The output contains $T$ lines, giving the answer for each test case in order. Each line contains a string representing the shortest replacement command. If there are multiple answers, output any one of them.

Examples

Input 1

2
abababa
cbc
abc
ab

Output 1

s/aba/c/g
s/c//g

Constraints

For 20% of the data, the length of the input strings does not exceed 50;

For 40% of the data, the length of the input strings does not exceed 200;

For 100% of the data, $T \le 10$, the length of the input strings does not exceed 2000, and the total length of the input does not exceed 10000 characters.