题目描述

小 Z 的死党小 K 是个强迫症，强迫症喜欢有规律的事物，比如回文。

死党之间经常恶搞，小 Z 想把手头的字符串稍微修改一下，使得其中没有任何回文的子串，再拿给小 K 看，专门让他难受！

求问小 Z 最少只需要修改多少位置，可以完成要求。

输入格式

第一行，$1$ 个正整数 $n$，表示初始字符串长度。

第二行，长度为 $n$ 的仅包含小写字母的字符串。

输出格式

第一行，$1$ 个整数，表示最少操作的次数，使得完成要求。

第二行，任一种可行的一种最小操作次数的方案。

输入输出样例

7
abacaba

2
abzcyba

样例 $\tt \#1$说明

• 改动 $2$ 个位置，比如 abzcyba 完成所求。

10
aaaaaaaaaa

6
abcabcabca

样例 $\tt \#2$说明

• 改动 $6$ 个位置比如 abcabcabca 完成所求。

数据范围

• 对于 $50\%$ 的数据，$n\le 100$
• 对于 $100\%$ 的数据，$2\le n\le 2\times10^5$