问题描述

高桥君在业余时间制作饰品。

饰品可以通过将 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 的方块，在右端添加一个写有 b 的方块。

高桥君可以选择在任意一步的后面结束制作饰品。如果结束制作，则给饰品起一个与饰品方块上的字母从左到右读相同的名字。

例如，如果在步骤 $0$、$1$、$2$、$3$ 后分别结束制作饰品，则饰品的名字分别为 b、abc、cabca、bcabcab。

给定字符串 $S$，判断它是否可以作为饰品的名字，如果可以的话，找出结束制作饰品时是在第几步。

输入

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

$N$ $S$

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

输出

如果字符串 $S$ 可以作为第 $K$ 步结束制作饰品的名字，则输出整数 $K$；如果无论何时结束制作饰品，饰品的名字都不是 $S$，则输出 -1。输出最后要换行。

输入示例1

3
abc

输出示例1

1

• 当在第 $1$ 步后结束制作饰品时，饰品的名字是 abc。

输入示例2

6
abcabc

输出示例2

-1

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

输入示例3

7
atcoder

输出示例3

-1

• 字符串 $S$ 中可能包含 a, b, c 之外的字符。

输入示例4

19
bcabcabcabcabcabcab

输出示例4

9