Consider the classic Towers of Hanoi problem, where there are ~N~ disks are on peg A and they need to be moved to peg C, with peg B as an intermediate place to store disks.

There are six possible moves that can be made - we denote xy as a move of the top disk from peg x to peg y. The six moves are therefore AB, AC, BA, BC, CA, and CB.

Assign each move a unique priority.

The claim is that one can blindly apply the following algorithm to solve the Towers of Hanoi problem:

while the problem is not yet solved:
    find the highest priority move that can be executed, such that a disk is not moved twice
        in two consecutive moves
    execute that move

Determine if it is possible to solve the Towers of Hanoi problem given the priorities present, and if so, count how many moves are executed in order to solve the problem. The disks may end up on peg B.

Constraints

~1 \le N \le 30~

Input Specification

The first line contains a single positive integer, ~N~.

The second and last line contains a permutation of the six moves. The first move has the highest priority and the last move has the lowest priority.

Output Specification

If it is impossible to solve the problem in finite time following the above algorithm, output -1. Otherwise, output the number of moves needed.

Sample Input

3
AB BC CA BA CB AC

Sample Output

7