AlgoLiga 2018

Kolejną sesję z algorytmiki studenci profesora Algobita mają już za sobą, niestety nie wszyscy. Niektórzy jeszcze raz będą musieli spotkać się z profesorem we wrześniu, no i jest Jasiu, którego historia jest następująca. Gdy wszedł na egzamin, profesor Algobit właśnie analizował ustawienie krążków wież Hanoi. Gdy zobaczył swojego ulubionego studenta  zaproponował mu układ. Powiedział, że jeśli Jasiu znajdzie sposób na określenie liczby ruchów, jakie trzeba wykonać aby otrzymać dane ustawienie krążków na trzech drążkach, to postawi mu najwyższą ocenę. Pomóż młodemu studentowi i rozwiąż ten problem.

Polega on na wypisaniu, po ilu ruchach optymalnego przestawiania krążków wież Hanoi otrzymamy dane ich ustawienie.

Wejście

W pierwszym wierszu jedna liczba k określająca liczbę krążków (0<k<21).

Następnie jedna liczba q oznaczająca liczbę zapytań (q<100000).

Każde zapytanie składa się z trzech wierszy oznaczających odpowiednio ustawienie krążków na pierwszym, drugim oraz trzecim słupku w następującym formacie:

najpierw jedna liczba n określająca liczbę krążków, następnie malejący ciąg n wielkich liter należących do przedziału [A..T].

Wyjście

Dla każdego zapytania jedna liczba określająca numer przestawienia krążków, które przedstawia zapytanie. Położenie pierwotne ma wartość 0.

Przykład

Wejście:
4
1
0
3 C B A
1 D
Wyjście:
8

Uwaga! Krążek pod numerem A ma najmniejszą średnicę oraz A < B < C < ... < T.