给你一个字符串$$$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”的非空前缀也作为 $$$s$$$ 中的子字符串出现在其他地方),因此算法终止。
执行算法后查找字符串的最终状态。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
接下来是 $$$t$$$ 行,每一行都包含一个测试用例的描述。每行包含一个字符串$$$s$$$。给定的字符串仅由英文字母表中的小写字母组成,长度在 $$$1$$$ 和 $$$2 \cdot 10^5$$$ 之间(含)。
保证所有测试用例$$$s$$$的长度总和不超过$$$2 \cdot 10^5$$$。
输出
对于每个测试用例,在执行算法后打印包含字符串 $$$s$$$ 的单行。可以证明这样的字符串非空。
示例
输入 #1
6 abcabdc a bbbbbbbbbb codeforces cffcfccffccfcffcfccfcffccffcfccf zyzyzwxxyyxxyyzzyzzxxwzxwywxwzxxyzzw
输出 #1
abdc a b deforces cf xyzzw
注意
第一个测试用例在语句中进行了解释。
在第二个测试用例中,无法对$$$s$$$执行任何操作。
在第三个测试用例中,
- 最初,$$$s =$$$“bbbbbbbbbb”。
- $$$1$$$ 操作后,$$$s =$$$ "b"。
在第四个测试用例中,
- 最初,$$$s =$$$“codeforces”。
- $$$1$$$ 操作后,$$$s =$$$“odeforces”。
- 在 $$$2$$$ 操作之后,$$$s =$$$“解除强制”。