背景

贪玩的sunnypig请Charles为他打造一个奇幻世界，Charles欣然答应了。然而一向善于出难题的Charles是决不会轻易让sunnypig轻松拥有一个奇幻世界的，于是Charles在建造过程中设置了重重机关，只有在sunnypig破解了这些障碍之后，才能尝试到奇幻世界中最有玩头的终极宝贝——时空穿梭机。虽然奇幻世界中其他的宝贝也很有趣，但贪玩的sunnypig怎能放过打boss的机会呢？于是他开始了破解障碍的旅程。

描述

第一道障碍来源于一种古老的游戏——汉诺塔。现在共有3根柱子，分别标号为A，B，C。初始时，A柱上共有n个直径递减的盘子从下往上垒。只有用最少步数将圆盘从A柱都移到C柱者才能获得胜利。游戏的规则是，任何时候大盘子不能放在小盘子的上面，任意一次移动都只能在A、B，B、C间，不能在A、C间直接移动。

然而在sunnypig面前的硕大汉诺塔中，圆盘并不全在A柱上，Charles给他出的难题是，让他判断，这是由初始状态向着目标状态经过多少次移动得到的状态。sunnypig席地而坐，进入深思……

格式

输入格式

本题有多组数据，对于每组数据：
第一行一个整数n（0<=n<=200，若n=0则表示输入结束）
第二行为n个字母（A or B or C），第k个字母表示直径第k大的盘子所在的柱子。字母中间无空格。

输出格式

对于每组测试数据输出一个整数，表示由初始状态，经多少次移动后产生的了输入的状态。如果输入状态不是由初始状态经最少移动次数到达终止状态过程的中间过程，则输出-1。

样例1

样例输入1

3
AAC
0

样例输出1

2

限制

各个测试点2s
不同测试点分数可能不同

来源

inspired by xiaomengxian