H. K-Similar Strings
time limit per test
2 seconds
memory limit per test
128 megabytes
input
standard input
output
standard output

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.

Input

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 ≤ 106), 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 × 105, inclusive. It is further guaranteed that the sum of lengths of A and B in all test cases does not exceed 3 × 106.

Output

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

Example
Input
4
3
ba
baa
2
aab
ab
1
acesrc
acesrc
100
roundgod
zyb
Output
yes
no
yes
no