354. Equivalent Strings

0

Medium

During the CodSule 2019 event in India, a tourist and Rajat were discussing problems related to divide and conquer. The tourist asked Rajat if he could determine whether two given strings, s1 and s2, are equivalent. Rajat inquired about the conditions for equivalence, to which the tourist replied:

Two strings, a and b, of equal length are considered equivalent under one of the following two cases:

- They are exactly the same.
- If we split string a into two equal halves, a1 and a2, and string b into two equal halves, b1 and b2, then one of the following conditions must be satisfied:
- a1 is equivalent to b1, and a2 is equivalent to b2
- a1 is equivalent to b2, and a2 is equivalent to b1

Rajat quickly solved the problem. Can you solve it too?

Input Format

The first line contains the number of test cases, t. Each test case consists of two strings of equal length.

Output Format

Print "YES" if the strings are "equivalent", and "NO" if they are not.

Example

Input

3
ababa
baaba
ab
ba
abc
abc

Output

NO
YES
YES

Constraints

1 <= test cases <= 10
1 <= string length <= 50000

Loading...

View Submissions

Console