本初字符串
题号：NC273233
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

定义一个字符串 S 的本初为 T，当且仅当 S 和 T 自我复制足够多的次数，使其长度相等后，对应位置相同的字符的位置，不小于复制之后的字符串的长度的一半，给定 S，求满足条件的 最短 的 T，若仍有多个相同长度的 T 满足条件，请输出其中 字典序最小 的 T。

形式化地讲，记一个字符串 S 的长度为 |S|，S 和 T 分别自我复制若干次产生的新字符串为 S' 和 T'，我们若称一个字符串 S 的本初为 T，需要满足

|S'| = |T'|

\sum_{1\leq i\leq |S'|}\Big[S'_i = T'_i\Big] \geq \frac{|S'|}{2}

请注意公式中并没有取整符号。

式子中出现的中括号为艾弗森括号，如果内部的表达式为真则值为 1，反之值为 0，例如 [1 = 1] 的值为 1，而 [1 = 0] 的值为 0。

一个新字符串 S' 是字符串 S 自我复制得来，可以认为对于任意 i\in [0, |S'|)，都有 S'_i = S_{i \% |S|}。

输入描述:

一行一个整数 T 表示数据组数，接下来每组数据一行一个字符串 S (\sum|S| \leq 2\times 10^5)，保证输入均为小写字母。

输出描述:

T 组数据，对于每组数据，一行一个字符串，表示 S 的本初。

示例1

输入

复制 
2
ab
abc

输出

复制 
a
aac

备注: