Evolution of Weasels solution codeforces

A wild basilisk just appeared at your doorstep. You are not entirely sure what a basilisk is and you wonder whether it evolved from your favorite animal, the weasel.

How can you find out whether basilisks evolved from weasels? Certainly, a good first step is to sequence both of their DNAs. Then you can try to check whether there is a sequence of possible mutations from the DNA of the weasel to the DNA of the basilisk.

Your friend Ron is a talented alchemist and has studied DNA sequences in many of his experiments. He has found out that DNA strings consist of the letters A, B and C and that single mutations can only remove or add substrings at any position in the string (a substring is a contiguous sequence of characters). The substrings that can be removed or added by a mutation are AA, BB, CC, ABAB or BCBC. During a sequence of mutations a DNA string may even become empty.

Evolution of Weasels solution codeforces

Ron has agreed to sequence the DNA of the weasel and the basilisk for you, but finding out whether there is a sequence of possible mutations that leads from one to the other is too difficult for him, so you have to do it on your own.

Input

Each test contains multiple test cases. The first line contains an integer 𝑡t (1≤𝑡≤1001≤t≤100) — the number of test cases. The descriptions of the 𝑡t test cases follow.

The first line of each test case contains a string 𝑢u (1≤|𝑢|≤2001≤|u|≤200) — the DNA of the weasel.

The second line of each test case contains a string 𝑣v (1≤|𝑣|≤2001≤|v|≤200) — the DNA of the basilisk.

The values |𝑢||u|, |𝑣||v| denote the lengths of the strings 𝑢u and 𝑣v. It is guaranteed that both strings 𝑢u and 𝑣v consist of the letters A, B and C.

Output

Evolution of Weasels solution codeforces

For each test case, print YES if there is a sequence of mutations to get from 𝑢u to 𝑣v and NO otherwise.

Example

input

Copy

8
A
B
B
C
C
A
AA
BB
BB
CC
CC
AA
ABAB
BCBC
ABC
CBA

output

Copy

NO
NO
NO
YES
YES
YES
YES
NO

Leave a Comment