Problem Statement

高橋君は趣味でアクセサリーを作っている。

アクセサリーは a, b, c のいずれか $1$ 文字が書かれたブロックを横 $1$ 列に並べることで作成できる。

高橋君は、以下の手順でアクセサリーの作成を行う：

• 手順 $0$ : 高橋君は b $1$ 文字からなるアクセサリーを作成する。

以降の手順では、既にあるアクセサリーの両端にブロックを $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$ が与えられるので、その文字列がアクセサリーの名前として考えられるかを判定し、考えられるなら何番目の手順の直後にアクセサリーの作成を終了したのかを求めよ。

Input

入力は以下の形式で標準入力から与えられる。

N
S

• $1$ 行目には、文字列 $S$ の長さを表す整数 $N (1 ≦ N ≦ 100)$ が与えられる。
• $2$ 行目には、半角の小文字アルファベットのみからなる文字列 $S$ が与えられる。

Output

文字列 $S$ が手順 $K$ の直後にアクセサリーの作成を終了したときのアクセサリーの名前と等しいような整数 $K$ が存在する場合は整数 $K$ を、いつアクセサリーの作成を終了してもアクセサリーの名前が $S$ とならないときは $-1$ を $1$ 行に出力せよ。出力の末尾にも改行を入れること。