Remove Adjacent Duplicates in Identifiers

You are given a list of identifier strings. For each identifier, repeatedly remove adjacent duplicate characters until no such duplicates remain. The operation works by scanning the string from left to right and removing a pair of adjacent identical characters. This process is applied iteratively until the string can no longer be reduced.

For example, given the identifier abbac, the adjacent duplicates bb are removed to get aa c; then the adjacent duplicates aa are removed to yield c. Implement an efficient solution using a stack-based approach.

The underlying idea can be expressed by the formula in LaTeX as follows: \(result = \text{reduce}(s)\), where the reduction removes any occurrence of \(xx\) for adjacent characters \(x\).

inputFormat

The input is read from stdin and consists of multiple lines. The first line contains an integer n, denoting the number of identifiers. Each of the following n lines contains a single identifier which is a non-empty string consisting of lowercase letters.

outputFormat

For each identifier, output the final string after all adjacent duplicate characters have been removed. Each result should be printed on a separate line to stdout.

## sample

4
abbac
aabbcc
abccba
abcdef

c
abcdef

</p>