题目描述

毛伊的鱼钩又坏了。这次他离特菲提太远了，无法让她帮忙修理。不过他知道一个咒语可以帮他（毕竟他是个半神）。

他一直随身携带这个咒语——它写在他衣服的一小块布上。但现在他后悔没有把这个咒语纹在身上——在长时间的航行中，字迹被水浸湿，有些字母变得难以辨认。毛伊试图辨认它们，最终得到了字符串 $s$，但总觉得有些不对劲。

他清楚地记得，在正确的咒语中没有任何子串是回文的，即从左到右和从右到左读起来都一样。他还确信他得到的字符串 $s$ 与原始咒语相差不大。

请帮助他确定需要在 $s$ 中替换的最小字母数量，使得其中不再包含回文子串。提醒一下，子串是指（在这种情况下，非空的）字符串中连续字符组成的序列。

输入格式

第一行包含一个整数 $n$——字符串 $s$ 的长度（$1 \le n \le 2 \cdot 10^5$）。

接下来是字符串 $s$，由 $n$ 个小写拉丁字母（从 a 到 z）组成——毛伊可能错误地辨认了其中某些字母的咒语。

输出格式

第一行输出一个整数 $k$——需要替换的最小字母数量。

然后在第二行输出一个由 a 到 z 字母组成的字符串 $s'$，该字符串与 $s$ 恰好有 $k$ 个字母不同，且不包含任何回文子串。

7
abacaba

2
abzcyba

10
aaaaaaaaaa

6
abcabcabca