Similar Strings

Problem Description

For two strings $A$ and $B$, we say $A$ and $B$ are similar if $A$ can be turned into $B$ by deleting one character, inserting one character, or modifying one character.

For instance, apple can become applee by inserting a character, can become appe by deleting a character, and can become bpple by modifying a character. So apple is similar to applee, appe, and bpple. But applee cannot be turned into bpple by any single such operation, so they are not similar.

In particular, two identical strings are also similar.

Given $T$ pairs of $A$ and $B$, determine for each pair whether they are similar.

Input Format

The first line contains a positive integer $T$. The next $T$ lines each contain two strings $A$ and $B$ separated by a space.

Output Format

For each pair $A$ and $B$, output similar if they are similar, otherwise output not similar.

Sample Input

5
apple applee
apple appe
apple bpple
applee bpple
apple apple

Sample Output

similar
similar
similar
not similar
similar

Sample Explanation

The sample contains $5$ test cases:

• Case 1: apple and applee. apple can become applee by inserting an e at the end, so they are similar.
• Case 2: apple and appe. apple can become appe by deleting l, so they are similar.
• Case 3: apple and bpple. apple can become bpple by changing a to b, so they are similar.
• Case 4: applee and bpple. applee cannot become bpple with a single delete/insert/modify operation, so they are not similar.
• Case 5: apple and apple. The two strings are identical, which also counts as similar.

So the outputs are similar, similar, similar, not similar, similar.

Constraints

For all test data, $1 \le T \le 100$, and the lengths of $A$ and $B$ are at most $50$. They contain only lowercase letters.