题目描述

一个字符串 $p$ 的重复数定义为最大的整数 $r$，使得 $p$ 可以分为 $r$ 段连续且相同的子串。比方说，$\texttt{ababab}$ 的重复数为 $3$，$\texttt{ababa}$ 的重复数为 $1$。

Your Task：

对于给定的串 $s$，找出 $s$ 的一个子串 $k$ 使得 $k$ 的重复数最大。

输入格式

第一行 $t$ 表示数据组数。

对于每组数据，一行中一个仅包含小写字母的字符串 $s$。

输出格式

对于每组数据，在一行中输出 $k$，如果有多个解，输出字典序最小的那一个。

2
ccabababc
daabbccaa

ababab
aa

数据规模与约定

对于 $100\%$ 的数据，$t \leq 10$，$|s| \leq 100000$。