本题没有可用的提交语言。

题目描述

一个字符串P的重复数定义为最大的整数R，使得P可以分为R段连续且相同的子串。比方说，“ababab”的重复数为3，“ababa”的重复数为1。 <o:p></o:p>

Your Task <o:p></o:p>

对于给定的串S，找出S的一个子串K使得K的重复数最大。 <o:p></o:p>

<o:p></o:p>

输入格式

第一行T表示数据组数 <o:p></o:p>

对于每组数据，一行中一个仅包含小写字母的字符串S <o:p></o:p>

<o:p></o:p>

输出格式

对于每组数据，在一行中输出K，如果有多个解，输出字典序最小的那一个 <o:p></o:p>

<o:p></o:p>

2 ccabababc daabbccaa

ababab aa

数据范围与约定

100%：T≤10，S的长度不超过100000