小泽先想出一个长度至少为 $2$ 的小写字符串 $a$。随后，他按从左到右的顺序写出 $a$ 的所有长度为 $2$ 的连续子串，再把这些子串直接连接成字符串 $b$。

例如，$a=$abac 的长度为 $2$ 的连续子串依次是 ab、ba、ac，所以 $b=$abbaac。

现在只给出按上述方法生成的 $b$。输入保证每个 $b$ 都确实由这种方法产生，并且原字符串 $a$ 唯一。小婷老师要从每组 $b$ 中恢复对应的 $a$。

刘老师提醒大家，连接时相邻子串之间没有分隔符，但输入保证来源合法。利用相邻片段共享的字符，就能按唯一顺序把原暗号完整拼回去。

输入格式

第一行输入测试组数 $t$。接下来 $t$ 行，每行包含一个字符串 $b$。

输出格式

输出 $t$ 行，第 $i$ 行是第 $i$ 组字符串 $b$ 对应的原字符串 $a$。

4
abbaac
ac
bccddaaf
zzzzzzzzzz

abac
ac
bcdaf
zzzzzz

1
abba

aba

2
xy
xxxy

xy
xxy

样例解释

样例 #1

第一组与题面中的 abac 示例一致；其余各组也按相邻二字符片段的连接关系逐步恢复。

样例 #2

abba 可分为 ab 和 ba，恢复出 aba。

样例 #3

xy 来自长度为 $2$ 的原串 xy；xxxy 可分为 xx、xy，恢复出 xxy。

数据范围与约定

• $1 \le t \le 1000$
• $2 \le |b| \le 100$
• $b$ 只包含小写英文字母
• 输入保证 $b$ 按题述方法生成，且答案唯一