给出一个长度为 $N (1 \le N \le 5000)$ 的字符串 $S$，且 $\forall S_i , S_i \in \{d,p \}$。

定义 $rotate (l,r)$，对于区间 $[l,r]$ 的每一个 $i$，重新赋值 $S_i$，使得 $S_i \not= S_{r+l-i}$ （即对称）。

需要执行 $0$ 或 $1$ 次 $rotate (l,r)$（$l,r$ 是任意的），使得 $S$ 字典序最小。