Cyclic Substring

Problem Description

A string $S$ is a cyclic substring of another string $T$ if and only if there exists some $k$ such that, after cyclically shifting $T$ right by $k$ positions to obtain a new string $T'$, $S$ is a substring of $T'$.

For example: abc is a cyclic substring of cefab (cefab shifted right by $2$ positions becomes abcef, and abc is a substring of abcef).

A string $P$ is a fully cyclic string if and only if for any substring $H$ of it, $H_{\text{reverse}}$ is a cyclic substring of $P$ ($H_{\text{reverse}}$ is the reversal of $H$, e.g. abc reversed is cba).

Given a string of length $n$, determine whether it is a fully cyclic string.

Input Format

The first line contains a positive integer $t$, the number of test cases.

For each test case, the first line contains a positive integer $n$, the length of the string. The next line contains a string of length $n$, consisting only of lowercase letters.

Output Format

For each test case, if the string is a fully cyclic string, output YES; otherwise output NO. Output a newline between consecutive test cases.

Sample Input

2
4
ccca
11
eeaafbddfaa

Sample Output

YES
NO

Constraints

For all data, $1 \le t \le 100$, $1 \le n \le 10^3$, and $\sum n \le 10^3$.

Hint

1. This problem can be solved with only basic syntax knowledge.
2. What does "any substring" mean?
3. If a substring contains another substring, can we just figure out the validity of the larger substring and infer the validity of the smaller one?
4. Think from larger substrings down to smaller ones: what is the largest substring?