405968: GYM102192 H K-Similar Strings

Acesrc loves solving string problems. He defined a relation called k-similarity between two nonempty strings.

The definition of k-similarity is shown below:

1. for nonempty string S, S and S are k-similar;
2. for two nonempty strings S and T with |S| + |T| ≤ k, if and are k-similar ( denotes string concatenation), then S and T are k-similar;
3. if S and T are k-similar, then and are k-similar, where P and Q are arbitrary (possibly empty) strings;
4. if S and U are k-similar, U and T are k-similar, then S and T are k-similar.

For example, aaa and aaa are 3-similar according to the the first condition. Hence, a and aa are 3-similar according to the second condition. Moreover, ba and baa, baa and baaa are also 3-similar, respectively, according to the third condition. Finally, ba and baaa are 3-similar, according to the fourth condition.

Now, given two strings A, B and an integer k, please determine whether A and B are k-similar.

The first line of the input is a single integer T (1 ≤ T ≤ 5000), denoting the number of test cases. Each test case contains three lines, which represent k (1 ≤ k ≤ 10⁶), A, B, respectively. It is guaranteed that A and B contain only lowercase letters 'a'-'z' and the lengths of A and B are between 1 and 2 × 10⁵, inclusive. It is further guaranteed that the sum of lengths of A and B in all test cases does not exceed 3 × 10⁶.

For each test case, display a single line: yes if A and B are k-similar, or no if they are not.

4
3
ba
baa
2
aab
ab
1
acesrc
acesrc
100
roundgod
zyb

yes
no
yes
no