You are given a string S$S$ with length N$N$. Determine if it is possible to find two non-empty strings A$A$ and B$B$ which satisfy the following conditions:

• A+B=S$A+B=S$, where +$+$ denotes string concatenation
• B$B$ is a substring of A$A$

Note: B$B$ is a substring of A$A$ if B$B$ can be obtained from A$A$ by deleting several (possibly zero) characters from the beginning and several (possibly zero) characters from the end. For example, "ab" is a substring of "cabd", but "ad" is not.

Input

• The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains a single integer N$N$.
• The second line contains a single string S$S$.

Output

For each test case, print a single line containing the string "YES" if it is possible to find strings A$A$ and