AlgoLiga 2018

Jasio, który swego czasu postanowił zostać włamywaczem, znów planuje napad na bank. Tym razem jednak musi to być włamanie, po którym nie zostanie żaden ślad (oczywiście oprócz braku zawartości sejfu). Aby przedsięwzięcie się udało, nasz bohater musi rozpracować zamek nowego typu, którym zabezpieczony jest sejf. Na szczęście, dzięki swoim rozległym znajomościom w świecie przestępczym, Jasiowi udało się zdobyć egzemplarz takiego zamka, więc może poddać go szczegółowej analizie.

Zamek składa się z pewnej liczby zasuwek (oznaczonych kolejnymi literami alfabetu), z których każda może przyjmować tylko dwie pozycje: "zamknięta" i "otwarta". Zasuwki są tak między sobą połączone, że w danym momencie można zmienić położenie tylko niektórych z nich. Jasio wie, że aby zamek otworzyć, trzeba zmieniać położenie zasuwek w określonej kolejności, tak aby w końcu wszystkie były otwarte. Po dotychczasowej analizie zauważył, że spełnione są dwie reguły:

1. położenie zasuwki można zmienić wtedy i tylko wtedy, gdy poprzednia zasuwka jest zamknięta, a wszystkie wcześniejsze są otwarte (jeśli więc na przykład zasuwki 'A' i 'B' są otwarte, a 'C' jest zamknięta, to wtedy możemy zmienić stan zasuwki 'D');
2. zawsze można zmienić położenie pierwszej zasuwki (oznaczonej literą 'A');

Jasio przećwiczył przestawianie zasuwek, więc teraz zmiana pozycji dowolnej z nich zajmuje mu już tylko sekundę. Jednak ponieważ czasu na miejscu będzie mało (na pewno nie więcej niż godzina), Jasiowi potrzebny jest program, który, w zależności od początkowego ustawienia zasuwek, wygeneruje najkrótszą sekwencję ruchów jakie należy w wykonać, aby otworzyć zamek. 

Wejście

W pierwszej linii liczba testów t (1 ≤ t ≤ 10000).

W kolejnych t liniach dane do pojedynczego testu w postaci opisanej poniżej.
Najpierw liczba całkowita n (1 ≤ n ≤ 26) oznaczająca liczbę zasuwek w zamku. Następnie liczba c (1 ≤ c ≤ 3600) oznaczająca czas (w sekundach) jaki ma Jasio na otwarcie zamka. Na koniec ciąg n początkowych liter angielskiego alfabetu, oznaczający początkowy stan zasuwek (wielka litera - zasuwka zamknięta, mała litera - zasuwka otwarta; co najmniej jedna z zasuwek jest zamknięta). 

Wyjście

Dla każdego testu, w osobnej linii ciąg liter angielskiego alfabetu oznaczający w jakiej kolejności należy zmieniać położenie zasuwek, aby otworzyć zamek najszybciej. Wielka litera oznacza, że daną zasuwkę należy otworzyć, a mała, że zamknąć. Jeśli jednak czas potrzebny na otwarcie zamka przekracza ten jaki ma Jasio, należy wypisać tylko "NIE DA RADY".

Przykład

Wejście:
3
2 10 AB
3 6 AbC
5 30 abcdE

Wyjście:
BA
bACaBA
NIE DA RADY