题目描述

Monocarp's current password on Codeforces is a string $s$ , consisting of lowercase Latin letters. Monocarp thinks that his current password is too weak, so he wants to insert exactly one lowercase Latin letter into the password to make it stronger. Monocarp can choose any letter and insert it anywhere, even before the first character or after the last character.

Monocarp thinks that the password's strength is proportional to the time it takes him to type the password. The time it takes to type the password is calculated as follows:

• the time to type the first character is $2$ seconds;
• for each character other than the first, the time it takes to type it is $1$ second if it is the same as the previous character, or $2$ seconds otherwise.

For example, the time it takes to type the password abacaba is $14$ ; the time it takes to type the password a is $2$ ; the time it takes to type the password aaabacc is $11$ .

You have to help Monocarp — insert a lowercase Latin letter into his password so that the resulting password takes the maximum possible amount of time to type.

输入格式

The first line contains one integer $t$ ( $1 \le t \le 1000$ ) — the number of test cases.

Each test case consists of one line containing the string $s$ ( $1 \le |s| \le 10$ ), consisting of lowercase Latin letters.

输出格式

For each test case, print one line containing the new password — a string which can be obtained from $s$ by inserting one lowercase Latin letter. The string you print should have the maximum possible required time to type it. If there are multiple answers, print any of them.

题目大意

题目描述

有一个由小写字母组成的字符串 $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