回文是向后读与向前读相同的字符串。例如,字符串“z”、“aaa”、“aba”和“abccba”是回文,但“codeforces”和“ab”不是回文。你讨厌回文,因为它们给你似曾相识的感觉。
有一个字符串$$$s$$$。您必须在 $$$s$$$ 中的某处插入一个字符“a”。如果可以创建一个不是回文的字符串,您应该找到一个示例。否则,你应该报告这是不可能的。
例如,假设 $$$s=$$$ "cbabc"。通过插入“a”,您可以创建“acbabc”、“cababc”、“cbaabc”、“cbabac”或“cbabca”。然而“cbaabc”是一个回文,因此您必须输出其他选项之一。
输入
第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。
每个测试用例中唯一的一行包含一个由小写英文字母组成的字符串$$$s$$$。
所有字符串的总长度不超过$$$3\cdot 10^5$$$。
输出
对于每个测试用例,如果没有解决方案,则输出“NO”。
否则,在下一行输出“YES”,后跟您构造的长度为 $$$|s|+1$$$ 的字符串。如果有多个解决方案,您可以打印任何一个。
您可以以任何大小写(大写或小写)打印“YES”和“NO”的每个字母。
示例
输入 #1
6 cbabc ab zza ba a nutforajaroftuna
输出 #1
YES cbabac YES aab YES zaza YES baa NO YES nutforajarofatuna
注意
语句中描述了第一个测试用例。
在第二个测试用例中,我们可以制作“aab”或“aba”。但“aba”是回文,因此“aab”是唯一正确的答案。
在第三个测试用例中,“zaza”和“zzaa”是正确答案,但“azza”不是。
在第四个测试用例中,“baa”是唯一正确的答案。
在第五个测试用例中,我们只能制作“aa”,这是一个回文。所以答案是“不”。
在第六个测试用例中,“anutforajaroftuna”是回文,但在其他地方插入“a”是有效的。