F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Isomorphic Strings

Time Limit: 8000/8000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 2616    Accepted Submission(s): 726


Problem Description
It is preferrable to read the pdf statment.

Two strings are called cyclical isomorphic if one can rotate one string to get another one. 'Rotate' here means ''to take some consecutive chars (maybe none) from the beginning of a string and put them back at the end of the string in the same order''. For example, string ''abcde'' can be rotated to string ''deabc''.

Now that you know what cyclical isomorphic is, Cuber QQ wants to give you a little test.

Here is a string $s$ of length $n$. Please check if $s$ is a concatenation of $k$ strings, $s_1,s_2,\cdots,s_k$ ($k>1$), where,

  • $k$ is a divisor of $n$;

  • $s_1,s_2,\ldots,s_k$ are of equal length: $\frac{n}{k}$;

  • There exists a string $t$, which is cyclical isomorphic with $s_i$ for all $1\le i\le k$.


Print ''Yes'' if the check is positive, or ''No'' otherwise.
 

Input
The first line contains an integer $T$ ($1\le T\le 1000$), denoting the number of test cases. $T$ cases follow.

  • The first line of each test case contains an integer $n$ ($1\le n \le 5 \cdot 10^6$).

  • The second line contains a string $s$ of length $n$ consists of lowercase letters only.


It is guaranteed that the sum of $n$ does not exceed $2\cdot 10^7$.
 

Output
For each test case, output one line containing ''Yes'' or ''No'' (without quotes).
 

Sample Input
6 1 a 2 aa 3 aab 4 abba 6 abcbcc 8 aaaaaaaa
 

Sample Output
No Yes No Yes No Yes
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-05-31 05:53:37, Gzip enabled