POLSKI SPOJ

Pan Cyferka to bardzo ceniony informatyk na świecie. Niedawno skonstruował komputer, w którym polecenia wydaje się poprzez wprowadzanie nieujemnych liczb całkowitych. Jedna liczba oznacza jedno polecenie na komputerze pana Cyferki. Np. liczba 7 oznacza polecenie “dodaj”. Natomiast zestaw złożony z kilku takich poleceń tworzy program. Pan Cyferka długo zastanawiał się nad zakodowaniem zestawu poleceń, tak aby tworzyły zwartą całość. Postanowił, że program będzie to liczba naturalna utworzona za pomocą funkcji:

  P(m[1],m[2],...,m[n])=f(m[1],f(m[2],f(m[3],...,f(m[n-1],m[n])...)))

gdzie

  f(a,b) = 2^a * (2*b+1) - 1

oraz m[1],m[2],...,m[n] to kolejne polecenia, z których składa się program.

Pan Cyferka był bardzo zadowolony ze swojego komputera i napisał kilka interesujących programów. Niestety niedawno wprowadził pewne zmiany w architekturze komputera i chciałby teraz zmienić swoje programy tak aby zaczęły działać na nowym sprzęcie. Jak się pewnie domyślasz Twoim zadaniem jest pomóc panu Cyferce przekonwertować programy, aby działały poprawnie na jego nowym komputerze.

Zadanie

Mając daną nieujemną liczbę całkowitą oznaczającą program (napisany przez Pana Cyferkę), napisz program który ją przekoduje, tak aby wyznaczała ten sam program na nowym komputerze. Sposób przekodowania polega na dodaniu do wartości liczbowej każdego polecenia pewnej nieujemnej liczby całkowitej.

Specyfikacja wejścia

W pierwszej linii wejścia podana jest dodatnia liczba całkowita, oznaczająca liczbę zestawów testowych, które dalej pojawią się na wejściu. W pierwszym wierszu każdego zestawu danych znajduje się jedna liczba całkowita N (2 ≤ N ≤ 10.000), oznaczająca liczbę poleceń zakodowanych w programie za pomocą funkcji P. W następnym wierszu znajduje się program przedstawiony w postaci nieujemnej liczby całkowitej zapisanej w systemie szesnastkowym (bez zer wiodących, oraz przy użyciu znaków 0..9, A..F), która może osiągnąć długość maksymalnie 100.000 cyfr (szesntatkowych oczywiście). W wierszach od 3 do N+2 zestawu znajdują się nieujemne liczby całkowite (zapisane w systemie dziesiętnym), o które należy zwiększyć po kolei każde polecenie w programie Pana Cyferki - polecenie m[i] należy zwiększyć o wartość podaną w wierszu i+2. Wiadomo, że zarówno suma tych liczb, jak i suma m[i] nie przekracza 500.000.

Specyfikacja wyjścia

Dla każdego zestawu danych pojawiającego się na wejściu należy wypisać liczbę szensnastkową, oznaczającą nowy program (ten który będzie działał na nowym komputerze Pana Cyferki).

Przykład

Wejście

3
3
1DF7
2
0
1
4
177
1
1
1
1
2
0
0
0

Wyjście

87DF
2DEF
0