该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

徐老师在整理一份字符串时，发现有些相邻的字符是相同的。他规定：如果字符串中某两个相邻位置的字符相同，就同时删除这两个字符。删除后左右两侧的字符合并，可能产生新的相邻相同字符，这时需要继续删除。

重复这个过程，直到字符串中不存在相邻的相同字符为止。请输出最终的字符串。

Format

Input

第一行一个正整数$T(1 \leq T \leq 10)$，表示测试组数。

接下来$T$行，每行一个仅包含小写字母的字符串$s(1 \leq |s| \leq 10^5)$。

Output

对于每组数据，输出一行，表示消除后的最终字符串。

Samples

2
abbaca
aabbcc

ca
(空行)

Limitation

1s, 1024KiB for each test case.