#3084. [Algorithmic Engagements 2011]The Shortest Period

内存限制:128 MiB 时间限制:10 Sec

题目描述

一个单词t被称为s的一个循环节当且仅当它的长度不超过t并且存在一个整数k使得s是t^k的一个前缀。比如entente的循环节是:ent,entent和entente。

Fotile在黑板上写下了一个很长的单词。Seter对Fotile的课不感兴趣,但是他把所有恰好在这个单词里删去一个字母的单词都写了下来。现在他想知道这些单词中拥有最短循环节的一个。


输入格式

第一行为数据组数d,不超过10。
每个数据包含一个数N及一个长为N的小写字母单词。

输出格式

最短循环节长度。

样例

样例输入


			
1
8 ababcaba

样例输出


			
2

数据范围与提示