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

Your Task：

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

输入格式

第一行 t 表示数据组数。

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

输出格式

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

输入数据 1

2
ccabababc
daabbccaa

输出数据 1

ababab
aa

数据规模与约定

对于 100% 的数据，t≤10，∣s∣≤100000。