说明

从左向右依次安放4根细柱A，B，C，D。在A柱上套有n(n<=20)个直径相同的圆盘，从下到上依次用连续的小写字母a,b,c,……编号，将这些圆盘经过B，C单向地移到D柱上（即不允许从右向左移动。圆盘可在B，C中暂存）。要求计算从A柱初始状态到D柱目标状态移动需要的最少步数。

输入格式

第一行是A柱上的圆盘总数，第二行是D柱上由下到上的圆盘的序列。

输出格式

最少的移动步数。如果无解，则输出"no solution!”

样例

3
abc

5