アメカーの部屋

时空限制#

C/C++: 1s/256MB

其他语言：2s/512MB

题目背景#

「吾一言可作恶，一言可行善，乃言灵之神。」

「我觉得『言灵』的力量，就是建立在个人心灵之上的，非常可怕的力量。」

「……说是愿望，不过是个约定而已。」

「『约定』是我们这些普通人也能使用的『言灵』。」

「你拥有很强大的力量，如果觉得这份力量没有用武之地，可以用来帮助他人。」

「用来守护他人的笑容与幸福。」

「这就是我的愿望。」

「约好了哟。」

​ ……

「这份约定，一定能保护好你的。」

​ ……

「言灵」是可以用语言操控他人的神能，其力量并不会根据言语的长度和正确性发生改变，而是根据承载了多少的思念。

题目描述#

语言可以简化为一个仅包含小写字母的字符串 $t$。诚想要将一段普通的语言 $t$ 重构为一段承载着思念的语句 $t'$。

一段语句 $t'$ 被认为是「承载着思念的」，当且仅当其满足以下两个核心条件：

1. 字符串 promise 必须是 $t'$ 的一个子串¹（Substring）。
2. $t'$ 必须是一个回文串²（Palindrome）。

为了成功重构言灵，诚必须遵守以下构造规则：

• $t'$ 必须仅由小写英文字母组成。

• $t'$ 的所有字符的权值之和必须严格等于原字符串 $t$ 的权值之和。即：$\sum w(t'_i) = \sum w(t_i)$。一个小写字母的权值为其 ASCII 码值减去 $96$。

• 为了保证言灵的精炼，$t'$ 的长度不能超过 $t$ 长度的两倍，即 $|t'| \le 2 \cdot |t|$。

请你帮助诚找到任意一个符合条件的言灵 $t'$。

输入格式#

第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。

对于每个测试用例：

• 仅一行包含一个字符串 $t$ ($8 \le |t| \le 2 \cdot 10^5$)，由小写英文字母组成，保证至少存在一个合法解。
• 数据保证所有测试用例的 $|t|$ 之和不超过 $2 \cdot 10^5$。

输出格式#

对于每个测试用例，输出一行字符串 $t'$。如果存在多个满足条件的字符串，你可以输出其中任意一个。

样例#

1
3
2
zazazazazazaza
3
zjwzaizunsgzzerzqd
4
becauseiloveyoudaze

1
aapromisesimorpaa
2
promisezezzezesimorp
3
japromiseabaesimorpaj

说明/提示#

样例 1 解释：

对于第一组样例，$\texttt{aapromisesimorpaa}$ 包含子串 $\texttt{promise}$ ，本身是回文串，且其字符权值和与原串相同，因此是一个合法答案。