回文自動雞是一種稀有的生物，其以發出的叫聲總是為回文而得名。一隻雞的叫聲可以用一段長度為 $L$ 的字串表示。具體來說，假設一隻雞的叫聲為 $s$，若 $s$ 的每一個長度為 $K$ 的子字串都是回文，則我們稱這隻雞為 $K$ 型回文自動雞。

今天你正走著自己的路，突然間路上衝出了一群雞並對你發出了各式各樣的叫聲。由於回文自動雞很稀有，你想仔細看看這群雞有沒有成為 $K$ 型回文自動雞的潛力。

首先，我們定義兩隻雞的差異程度如下：假設兩隻雞的叫聲分別為 $s$ 及 $t$，則牠們的差異程度 $d(s, t)$ 為，對於所有 $1 \le i \le L$，滿足 $s_i \ne t_i$ 的整數 $i$ 數量。接下來定義一隻雞能成為 $K$ 型回文自動雞的潛力如下：假設該隻雞的叫聲為 $s$，而所有 $K$ 型回文自動雞的叫聲分別為 $t_1, t_2, \cdots$，則該隻雞能成為 $K$ 型回文自動雞的潛力為 $L - \min(d(s, t_i))$，也就是 $L$ 減去 $s$ 與所有 $t_i$ 的差距之中的最小值。

舉例來說，假設 $L=3$，而某隻雞的叫聲為 $\texttt{aba}$。其成為 $K=2$ 型回文自動雞的潛力為 $3-1 = 2$，因為其叫聲與 $\texttt{aaa}$ 這隻 $K$ 型回文自動雞的差距為 $1$，是所有 $K$ 型回文自動雞之中最小的。

為了找出稀有的回文自動雞，請你寫一支程式快速的算出每一隻雞成為回文自動雞的潛力。