#P1730D. Prefixes and Suffixes

    ID: 8062 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>constructive algorithmsstringstwo pointers*2200

Prefixes and Suffixes

Description

You have two strings s1s_1 and s2s_2 of length nn, consisting of lowercase English letters. You can perform the following operation any (possibly zero) number of times:

  • Choose a positive integer 1kn1 \leq k \leq n.
  • Swap the prefix of the string s1s_1 and the suffix of the string s2s_2 of length kk.

Is it possible to make these two strings equal by doing described operations?

The first line contains a single integer tt (1t1041 \le t \le 10^4) — the number of test cases. Then the test cases follow.

Each test case consists of three lines.

The first line contains a single integer nn (1n1051 \le n \le 10^5) — the length of the strings s1s_1 and s2s_2.

The second line contains the string s1s_1 of length nn, consisting of lowercase English letters.

The third line contains the string s2s_2 of length nn, consisting of lowercase English letters.

It is guaranteed that the sum of nn for all test cases does not exceed 21052 \cdot 10^5.

For each test case, print "YES" if it is possible to make the strings equal, and "NO" otherwise.

Input

The first line contains a single integer tt (1t1041 \le t \le 10^4) — the number of test cases. Then the test cases follow.

Each test case consists of three lines.

The first line contains a single integer nn (1n1051 \le n \le 10^5) — the length of the strings s1s_1 and s2s_2.

The second line contains the string s1s_1 of length nn, consisting of lowercase English letters.

The third line contains the string s2s_2 of length nn, consisting of lowercase English letters.

It is guaranteed that the sum of nn for all test cases does not exceed 21052 \cdot 10^5.

Output

For each test case, print "YES" if it is possible to make the strings equal, and "NO" otherwise.

Samples

样例输入 1

<div class="test-example-line test-example-line-even test-example-line-0">7</div><div class="test-example-line test-example-line-odd test-example-line-1">3</div><div class="test-example-line test-example-line-odd test-example-line-1">cbc</div><div class="test-example-line test-example-line-odd test-example-line-1">aba</div><div class="test-example-line test-example-line-even test-example-line-2">5</div><div class="test-example-line test-example-line-even test-example-line-2">abcaa</div><div class="test-example-line test-example-line-even test-example-line-2">cbabb</div><div class="test-example-line test-example-line-odd test-example-line-3">5</div><div class="test-example-line test-example-line-odd test-example-line-3">abcaa</div><div class="test-example-line test-example-line-odd test-example-line-3">cbabz</div><div class="test-example-line test-example-line-even test-example-line-4">1</div><div class="test-example-line test-example-line-even test-example-line-4">a</div><div class="test-example-line test-example-line-even test-example-line-4">a</div><div class="test-example-line test-example-line-odd test-example-line-5">1</div><div class="test-example-line test-example-line-odd test-example-line-5">a</div><div class="test-example-line test-example-line-odd test-example-line-5">b</div><div class="test-example-line test-example-line-even test-example-line-6">6</div><div class="test-example-line test-example-line-even test-example-line-6">abadaa</div><div class="test-example-line test-example-line-even test-example-line-6">adaaba</div><div class="test-example-line test-example-line-odd test-example-line-7">8</div><div class="test-example-line test-example-line-odd test-example-line-7">abcabdaa</div><div class="test-example-line test-example-line-odd test-example-line-7">adabcaba</div>

样例输出 1

YES
YES
NO
YES
NO
NO
YES

Note

In the first test case:

  • Initially s1=cbcs_1 = \mathtt{cbc}, s2=abas_2 = \mathtt{aba}.
  • Operation with k=1k = 1, after the operation s1=abcs_1 = \mathtt{abc}, s2=abcs_2 = \mathtt{abc}.

In the second test case:

  • Initially s1=abcaas_1 = \mathtt{abcaa}, s2=cbabbs_2 = \mathtt{cbabb}.
  • Operation with k=2k = 2, after the operation s1=bbcaas_1 = \mathtt{bbcaa}, s2=cbaabs_2 = \mathtt{cbaab}.
  • Operation with k=3k = 3, after the operation s1=aabaas_1 = \mathtt{aabaa}, s2=cbbbcs_2 = \mathtt{cbbbc}.
  • Operation with k=1k = 1, after the operation s1=cabaas_1 = \mathtt{cabaa}, s2=cbbbas_2 = \mathtt{cbbba}.
  • Operation with k=2k = 2, after the operation s1=babaas_1 = \mathtt{babaa}, s2=cbbcas_2 = \mathtt{cbbca}.
  • Operation with k=1k = 1, after the operation s1=aabaas_1 = \mathtt{aabaa}, s2=cbbcbs_2 = \mathtt{cbbcb}.
  • Operation with k=2k = 2, after the operation s1=cbbaas_1 = \mathtt{cbbaa}, s2=cbbaas_2 = \mathtt{cbbaa}.

In the third test case, it's impossible to make strings equal.