問題文
高桥制作配饰是一种爱好。
配件 a, b, c 任何一个 1 水平方向写有字母的块 1 可以通过将它们排列在列中来创建。
Takahashi 使用以下步骤创建配件:
- 手順 0 :高桥先生
b1 创建一个由字母制成的配件。
在以下步骤中,我们将在现有配件的两端添加块。 1 通过一一添加来修改配件。
- 手順 3n + 1 (n ≧ 0) : 手順 3n 完成的配件左端将有文字。
将带有
a的块移动到右端。 添加一个写有c的块。 - 手順 3n + 2 (n ≧ 0) : 手順 3n+1 完成的配件左端将有文字。
将带有
c的块移动到右端。 添加一个写有a的块。 - 手順 3n (n ≧ 1) : 手順 3n-1 完成的配件左端将有文字。
将带有
b的块移动到右端。 添加一个写有b的块。
高桥可以在他喜欢的任何步骤后立即完成配件的制作。完成后,配件的名称与构成配件的块上写的字母相同,从左到右读取。
例如,过程 0, 1, 2, 3 如果您在每个配件之后立即完成创建配件,则该配件的名称将为b, abc, cabca, bcabcab 变为。
给定了
文字列 S ,判断该字符串是否可以被认为是配件的名称,如果是,则找出该配件的创建是在哪一步结束的。
入力
输入是按以下格式从标准输入给出的。
N S
- 1 行包含字符串 S 长度的整数 N (1 ≦ N ≦ 100) 。
- 2 行包含仅由半角小写字母组成的字符串。 S 。
出力
文字列 S 是程序 当您在 K 之后立即完成配件创建时,等于配件名称的整数 如果存在 K ,则为整数 K ,无论你什么时候完成饰品的创建,饰品的名称都不会改变。 如果 S 没有发生, 当您在 -1 在 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