Problem Description

Takahashi enjoys making accessories as a hobby.

An accessory can be created by arranging blocks, each labeled with one of the characters a, b, or c, in a horizontal row.

Takahashi creates accessories following these steps:

• Step $ 0 $: Takahashi creates an accessory consisting of a single character b.

In the subsequent steps, he modifies the existing accessory by adding one block to each end:

• Step $3n\ +\ 1\ (n\ ≧\ 0)$: After completing step $ 3n $, he adds a block labeled a to the left end and a block labeled c to the right end.
• Step $3n\ +\ 2\ (n\ ≧\ 0)$: After completing step $ 3n+1 $, he adds a block labeled c to the left end and a block labeled a to the right end.
• Step $3n\ (n\ ≧\ 1)$: After completing step $ 3n-1 $, he adds a block labeled b to the left end and a block labeled b to the right end.

Takahashi can end the creation of the accessory at any step. If he ends it, the accessory is named by reading the characters on the blocks from left to right.

For example, if he ends the creation after steps $ 0 $, $ 1 $, $ 2 $, and $ 3 $, the names of the accessories will be b, abc, cabca, and bcabcab, respectively.

Given a string $ S $, determine if it can be the name of an accessory. If it can, find out after which step the creation of the accessory was ended.

Input Format

The input is provided from the standard input in the following format:

$ N $ $ S $

• The first line contains an integer $N\ (1\ ≦\ N\ ≦\ 100)$, representing the length of the string $ S $.
• The second line contains a string $ S $ consisting of lowercase alphabetic characters.

Output Format

If there exists an integer $ K $ such that the string $ S $ is the name of the accessory after ending the creation at step $ K $, output the integer $ K $. If it is impossible for the accessory's name to be $ S $ at any step, output $ -1 $. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

3
abc

Sample Output #1

1

Sample Input #2

6
abcabc

Sample Output #2

-1

Sample Input #3

7
atcoder

Sample Output #3

-1

Sample Input #4

19
bcabcabcabcabcabcab

Sample Output #4

9

Notes/Hints

Sample Explanation 1

• The name of the accessory after ending the creation at step $ 1 $ is abc.

Sample Explanation 2

• The string abcabc cannot be the name of an accessory.

Sample Explanation 3

• The string $ S $ may contain characters other than a, b, and c.

见题面 Input 部分

见题面 Output 部分