Bob 先构造一个仅由小写英文字母组成的秘密字符串 $a$，其长度满足 $|a|\ge 2$。 随后他用 $a$ 构造字符串 $b$ 并交给 Alice，让她根据 $b$ 还原 $a$。

构造规则如下： 按从左到右的顺序写出 $a$ 的所有长度为 $2$ 的子串，并按该顺序依次拼接起来得到 $b$。 也就是依次取：

• $a[1..2], a[2..3], \dots, a[|a|-1..|a|]$ 并将它们连接成 $b$。

例如：$a=\text{"abac"}$，其长度为 $2$ 的子串依次为 "ab", "ba", "ac"，因此 $b=\text{"abbaac"}$。

现在给定字符串 $b$。请你输出 Bob 构造的唯一的字符串 $a$。题目保证 $b$ 一定由上述规则生成，且答案唯一。

输入格式

第一行一个整数 $t$（$1\le t\le 1000$），表示测试用例数量。 接下来 $t$ 行，每行一个字符串 $b$（$2\le |b|\le 100$），由小写英文字母组成。

输出格式

输出 $t$ 行，每行输出对应测试用例的秘密字符串 $a$。

样例

输入

4
abbaac
ac
bccddaaf
zzzzzzzzzz

输出

abac
ac
bcdaf
zzzzzz

说明

• 若 $|a|=2$，则只有一个长度为 $2$ 的子串，因此 $b=a$。
• 题目保证每个用例的答案唯一。