一个字符串 的重复数定义为最大的整数 ，使得 可以分为 段连续且相同的子串。比方说， 的重复数为 ， 的重复数为 。
Your Task：
对于给定的串 ，找出 的一个子串 使得 的重复数最大。
第一行 表示数据组数。
对于每组数据，一行中一个仅包含小写字母的字符串 。
对于每组数据，在一行中输出 ，如果有多个解，输出字典序最小的那一个。
2 ccabababc daabbccaa
ababab aa
对于 的数据，，。
