题目描述

有一个由小写字母组成的字符串 $s$，你可以在其任意位置插入一个小写字母（包括最前面和最后面），请最大化其权值。你只需要输出任意权值最大的新字符串。

其中，字符串的权值定义如下计算：

• 若某个字符前面没有字符，或前面的字符与其不同，则其为字符串贡献 $2$ 点权值。

• 若某个字符前面的字符与其相同，则其为字符串贡献 $1$ 点权值。

输入格式

第一行输入一个整数 $t(1\le t\le 1000)$，表示测试组数。

接下来 $t$ 行，每行一个字符串 $s(1\le\lvert s\rvert\le 10)$，表示待处理的字符串。

输出格式

输出共 $t$ 行，每行一个字符串，第 $i$ 行输出第 $i$ 组测试数据的答案。

样例

4
a
aaa
abb
password

wa
aada
abcb
pastsword