AT_abc023_b.[ABC023B] 手芸王

高桥君的兴趣是制作饰品。

饰品可以通过将写有 a、b 或 c 的方块横向排列一行来制作。

高桥君按照以下步骤制作饰品：

• 步骤 $0$：高桥君制作一个仅包含一个字符 b 的饰品。

之后的每一步，他会在已有饰品的两端各添加一个方块，对饰品进行改造。

• 步骤 $3n+1\ (n\geq 0)$：在步骤 $3n$ 完成的饰品左端添加写有 a 的方块，右端添加写有 c 的方块。
• 步骤 $3n+2\ (n\geq 0)$：在步骤 $3n+1$ 完成的饰品左端添加写有 c 的方块，右端添加写有 a 的方块。
• 步骤 $3n\ (n\geq 1)$：在步骤 $3n-1$ 完成的饰品左端和右端各添加写有 b 的方块。

高桥君可以在任意一个步骤结束后停止制作饰品。停止后，饰品的名字就是从左到右依次读取饰品方块上字符得到的字符串。

例如，在步骤 $0$、$1$、$2$、$3$ 结束时，饰品的名字依次为 b、abc、cabca、bcabcab。

现在给定一个字符串 $S$，请判断该字符串是否可能作为某一步骤结束时饰品的名字。如果可以，输出在第几步结束时得到该名字；如果不可以，输出 $-1$。

输入从标准输入中按以下格式给出。

$N$ $S$

• 第 $1$ 行给出一个整数 $N$，表示字符串 $S$ 的长度，$1\leq N\leq 100$。
• 第 $2$ 行给出仅由小写英文字母组成的字符串 $S$。

如果存在某个整数 $K$，使得在步骤 $K$ 结束时饰品的名字等于字符串 $S$，则输出该整数 $K$；如果无论在哪一步结束饰品的制作，饰品的名字都不等于 $S$，则输出 $-1$。输出末尾需换行。

样例解释 1

• 在步骤 $1$ 结束时饰品的名字为 abc。

样例解释 2

• 字符串 abcabc 不可能作为饰品的名字。

样例解释 3

• 字符串 $S$ 可能包含除 a、b、c 以外的字符。

由 ChatGPT 4.1 翻译