← 返回题目列表

Codeforces · 1997/A

A. 强密码

中文机器翻译题面 查看原题

Monocarp 在 Codeforces 上的当前密码是字符串 $$$s$$$,由小写拉丁字母组成。 Monocarp 认为他当前的密码太弱,因此他想在密码中恰好插入一个小写拉丁字母以使其更强。 Monocarp 可以选择任何字母并将其插入到任何位置,甚至可以在第一个字符之前或最后一个字符之后。

Monocarp 认为密码的强度与他输入密码所花费的时间成正比。输入密码所需的时间计算如下:

- 输入第一个字符的时间为 $$$2$$$ 秒;
- 对于第一个字符以外的每个字符,如果与前一个字符相同,则键入该字符所需的时间为 $$$1$$$ 秒,否则为 $$$2$$$ 秒。

例如,输入密码abacaba所需的时间为$$$14$$$;输入密码a所需的时间为$$$2$$$;输入密码 aaabacc 所需的时间为 $$$11$$$。

你必须帮助 Monocarp — 在他的密码中插入一个小写拉丁字母,以便在尽可能多的时间内输入密码。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例由一行包含字符串 $$$s$$$ ($$$1 \le |s| \le 10$$$) 组成,该字符串由小写拉丁字母组成。

输出

对于每个测试用例,打印一行包含新密码 - 可以通过插入一个小写拉丁字母从 $$$s$$$ 获得的字符串。您打印的字符串应该有尽可能长的键入时间。如果有多个答案,请打印其中任何一个。

示例

输入 #1

4
a
aaa
abb
password

输出 #1

wa
aada
abcb
pastsword