AlgoLiga 2018

Wimbledon

Jasiu jest wielbicielem tenisa ziemnego i stara się nie opuszczać żadnego ważnego turnieju. Podczas gdy Ty rozwiązujesz zadania algorytmiczne, on zasiada na trybunach Wimbledonu i podziwia kunszt tenisistów, popijając przy tym chłodny napój orzeźwiający. Jasiu przed turniejem każdemu zawodnikowi przyporządkowuje numer porządkowy od 1 do n, po czym śledzi i koduje wyniki kolejnych spotkań na swój własny sposób. Rysuje drabinkę turniejową i uzupełnia pierwszą kolumnę kolejnymi liczbami reprezentującymi zawodników. W pierwszej rundzie zawodnik z numerem nieparzystym gra z zawodnikiem z numerem o jeden większym. Jeśli w pojedynku meczowym wygra zawodnik umiejscowiony w drabince nad przeciwnikiem, Jasiu wynik tego spotkania oznacza literą A, w przeciwnym razie literą B. W ten sposób powstaje ciąg złożony z liter A lub B w kolejności rozgrywania meczów.



Powyżej przykład trzyrundowego turnieju złożonego z siedmiu meczów, w którym brało udział ośmiu zawodników. Jasiu turniej ten zakodował jako ciąg ABAAABB, po czym w swoim notatniku zapisał liczbę zawodników biorących udział w turnieju i dany ciąg. Jasiu często wspomina i opowiada o turniejach, ale nie zawsze pamięta zwycięzców, wtedy posiłkuje się swoim notatnikiem i próbuje odkodować tę informację. Czy jesteś w stanie pomóc Jasiowi?


Wejście
W pierwszym wierszu podana jest liczba d (1 ≤ d ≤ 100) turniejów, o których opowiada Jasiu.
Każdy turniej opisany jest w dwóch wierszach. W pierwszym wierszu podana jest liczba zawodników biorących udział w turnieju n = 2^k, gdzie 1 ≤ k ≤ 20. W wierszu drugim podany jest zakodowany ciąg złożony z n-1 liter.
Pliki wejściowe nie przekraczają 10 MB.

Wyjście
Dla każdego zapytania w osobnym wierszu jedna liczba - numer porządkowy zwycięzcy.

Przykład

Wejście
3
8
ABAAABB
16
ABAAAABBAAABABB
32
ABAABBBAAABABABBABAAAAAAAAAABAA

Wyjście
7
16
10