有一个字符串$$$a$$$(你不知道),由小写拉丁字母组成,按照以下规则加密为字符串$$$s$$$:
- 在字符串 $$$a$$$ 的每个字符之后,添加与字符本身不同的任意数量(可能为零)的任何小写拉丁字母;
- 每次添加后,都会添加我们补充的字符。
给定字符串$$$s$$$,你需要输出初始字符串$$$a$$$。换句话说,您需要解密字符串$$$s$$$。
请注意,以这种方式加密的每个字符串都是唯一解密的。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100$$$) — 加密消息的长度。
每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$ — 从某个字符串 $$$a$$$ 获得的加密消息。
输出
对于每个测试用例,在单独的行上输出解密消息 $$$a$$$。
示例
输入 #1
3 8 abacabac 5 qzxcq 20 ccooddeeffoorrcceess
输出 #1
ac q codeforces
注意
在第一条加密消息中,字母$$$a$$$被加密为$$$aba$$$,字母$$$c$$$被加密为$$$cabac$$$。
在第二条加密消息中,只有一个字母$$$q$$$被加密为$$$qzxcq$$$。
在第三条加密消息中,每个字母中添加零个字符。