K-Similar Strings

Acesrc loves solving string problems. He defined a relation called $\textit{k-similarity}$ between two $\textbf{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| \leq k$, if $S \circ T$ and $T \circ S$ are $k$-similar ($\circ$ denotes string concatenation), then $S$ and $T$ are $k$-similar;
3. if $S$ and $T$ are $k$-similar, then $P \circ S \circ Q$ and $P \circ T \circ Q$ 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, $\texttt{aaa}$ and $\texttt{aaa}$ are 3-similar according to the the first condition. Hence, $\texttt{a}$ and $\texttt{aa}$ are 3-similar according to the second condition. Moreover, $\texttt{ba}$ and $\texttt{baa}$, $\texttt{baa}$ and $\texttt{baaa}$ are also 3-similar, respectively, according to the third condition. Finally, $\texttt{ba}$ and $\texttt{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 \leq T \leq 5000)$, denoting the number of test cases. Each test case contains three lines, which represent $k$ $(1 \leq k \leq 10^6)$, $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 \times 10^5$, inclusive. It is further guaranteed that the sum of lengths of $A$ and $B$ in all test cases does not exceed $3 \times 10^6$.

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

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

yes
no
yes
no

2018 Multi-University Training Contest 8