Similar Strings Problem Statement

Determine whether two given strings, A and B, both of length N, are similar by returning a 1 if they are, otherwise return a 0.

Explanation:

String A is similar to string B if the following conditions are met:

1. A is equal to B.
2. Both strings can be divided into two halves, A1, A2 and B1, B2, having equal lengths, such that at least one of the following is true:
   • A1 is similar to B1 and A2 is similar to B2.
   • A1 is similar to B2 and A2 is similar to B1.

Input:

The first line contains a single integer 'T', indicating the number of test cases.
For each test case, there are two space-separated strings: A and B.

Output:

For each test case, print 1 if 'A' is similar to 'B', otherwise print 0. Each result should be printed on a new line.

Example:

Input:
2
abcd dbca
abdc abcd

Output:
1
1

Constraints:

• 1 ≤ T ≤ 5
• 1 ≤ |A| = |B| ≤ 3000
• Both A and B consist of only lowercase English letters.
• Time limit: 1 second

Note:

You are not required to print anything; the task is to implement the given function and return the result.