Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_08_10 - Wimbledon

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 = 2k, 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


Dodane przez:Mariusz Śliwiński
Data dodania:2013-06-28
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.