题目描述

给定一个只包含小写英文字母的字符串 $s$。你需要对 $s$ 执行如下算法：

• 令 $x$ 为 $s$ 的最长前缀的长度，该前缀在 $s$ 的其它位置也作为连续子串出现（该出现可以与前缀有重叠）。如果 $x=0$，则算法终止。否则，删除 $s$ 的前 $x$ 个字符，并重复上述过程。

前缀是指由字符串的前若干个字母组成的字符串，顺序不能改变。空前缀也是合法的前缀。例如，字符串 "abcd" 有 5 个前缀：空串，"a"，"ab"，"abc" 和 "abcd"。

例如，对 $s =$ "abcabdc" 执行该算法：

• 初始时，"ab" 是同时在 $s$ 其它地方出现的最长前缀，因此第 1 次操作后 $s =$ "cabdc"。
• 然后，"c" 是同时在 $s$ 其它地方出现的最长前缀，因此第 2 次操作后 $s =$ "abdc"。
• 现在 $x=0$（因为 "abdc" 没有非空前缀在其它地方作为子串出现），算法终止。

请输出执行完算法后字符串的最终状态。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

接下来有 $t$ 行，每行一个字符串 $s$。每个字符串只包含小写英文字母，长度在 $1$ 到 $2 \cdot 10^5$ 之间。

保证所有测试用例中字符串的总长度不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行，表示执行完算法后的字符串。可以保证该字符串非空。

说明/提示

第一个测试用例的过程在题目描述中已给出。

第二个测试用例中，无法对 $s$ 进行任何操作。

第三个测试用例：

• 初始时，$s =$ "bbbbbbbbbb"。
• 第 1 次操作后，$s =$ "b"。

第四个测试用例：

• 初始时，$s =$ "codeforces"。
• 第 1 次操作后，$s =$ "odeforces"。
• 第 2 次操作后，$s =$ "deforces"。

由 ChatGPT 4.1 翻译

样例

6
abcabdc
a
bbbbbbbbbb
codeforces
cffcfccffccfcffcfccfcffccffcfccf
zyzyzwxxyyxxyyzzyzzxxwzxwywxwzxxyzzw

abdc
a
b
deforces
cf
xyzzw