An encoder encodes the first $16$ lowercase English letters using $4$ bits each. The first bit (from the left) of the code is $0$ if the letter lies among the first $8$ letters, else it is $1$, signifying that it lies among the last $8$ letters. The second bit of the code is $0$ if the letter lies among the first $4$ letters of those $8$ letters found in the previous step, else it's $1$, signifying that it lies among the last $4$ letters of those $8$ letters. Similarly, the third and the fourth bit each signify the half in which the letter lies. 
For example, the letter $j$ would be encoded as :
- Among $(a,b,c,d,e,f,g,h$ $|$ $i,j,k,l,m,n,o,p)$, $j$ appears in the second half. So the first bit of its encoding is $1$.
- Now, among $(i,j,k,l$ $|$ $m,n,o,p)$, $j$ appears in the first half. So the second bit of its encoding is $0$.
- Now, among $(i,j$ $|$ $k,l)$, $j$ appears in the first half. So the third bit of its encoding is $0$.
- Now, among $(i$ $|$ $j)$, $j$ appears in the second half. So the fourth and last bit of its encoding is $1$.
So $j$'s encoding is $1001$,
Given a binary encoded string $S$, of length at most $10^5$, decode the string. That is, the first 4 bits are the encoding of the first letter of the secret message, the next 4 bits encode the second letter, and so on. It is guaranteed that the string's length is a multiple of 4.

-----Input:-----
- The first line of the input contains an integer $T$, denoting the number of test cases.
- The first line of each test case contains an integer $N$, the length of the encoded string.
- The second line of each test case contains the encoded string $S$.

-----Output:-----
For each test case, print the decoded string, in a separate line.

-----Constraints-----
- $1 \leq T \leq 10$
- $4 \leq N \leq 10^5$
- The length of the encoded string is a multiple of $4$.
- $0 \le S_i \le 1$

-----Subtasks-----
- $100$ points : Original constraints. 

-----Sample Input:-----
3
4
0000
8
00001111
4
1001

-----Sample Output:-----
a
ap
j

-----Explanation:-----
- Sample Case $1$ : 
The first bit is $0$, so the letter lies among the first $8$ letters, i.e., among $a,b,c,d,e,f,g,h$. The second bit is $0$, so it lies among the first four of these, i.e., among $a,b,c,d$. 
The third bit is $0$, so it again lies in the first half, i.e., it's either $a$ or $b$. Finally, the fourth bit is also $0$, so we know that the letter is $a$.
- Sample Case $2$ : 
Each four bits correspond to a character. Just like in sample case $1$, $0000$ is equivalent to $a$. Similarly, $1111$ is equivalent to $p$. So, the decoded string is $ap$.
- Sample Case $3$ : 
The first bit is $1$, so the letter lies among the last $8$ letters, i.e., among $i,j,k,l,m,n,o,p$. The second bit is $0$, so it lies among the first four of these, i.e., among $i,j,k,l$. 
The third bit is $0$, so it again lies in the first half, i.e., it's either $i$ or $j$. Finally, the fourth bit is $1$, so we know that the letter is $j$.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import sys\nimport math\n\n\nclass Test:\n N=0\n S=[]\n def __init__(self):\n  tmp=input().split()\n  self.N=int(tmp[0])\n  self.S=[int(i) for i in input()]\n\nclass Input:\n T=0\n test=[]\n def __init__(self):\n  self.T=int(input())\n  for i in range(0,self.T):\n   self.test.append(Test())\n\nletter=[]\nletter.append([])\nletter.append([])\nletter[0].append([])\nletter[0].append([])\nletter[1].append([])\nletter[1].append([])\nletter[0][0].append([])\nletter[0][0].append([])\nletter[0][1].append([])\nletter[0][1].append([])\nletter[1][0].append([])\nletter[1][0].append([])\nletter[1][1].append([])\nletter[1][1].append([])\n\nletter[0][0][0].append("a")\nletter[0][0][0].append("b")\nletter[0][0][1].append("c")\nletter[0][0][1].append("d")\nletter[0][1][0].append("e")\nletter[0][1][0].append("f")\nletter[0][1][1].append("g")\nletter[0][1][1].append("h")\nletter[1][0][0].append("i")\nletter[1][0][0].append("j")\nletter[1][0][1].append("k")\nletter[1][0][1].append("l")\nletter[1][1][0].append("m")\nletter[1][1][0].append("n")\nletter[1][1][1].append("o")\nletter[1][1][1].append("p")\ndef getletter(i, j, k, l):\n return letter[i][j][k][l]\n\ndef test_case(t:Test):\n sum=0\n i=0\n string=""\n while i + 3 < len(t.S):\n  string+=getletter(t.S[i], t.S[i+1], t.S[i+2],t.S[i+3])\n  i+=4\n print(string)\n\ninp=Input()\nfor test in inp.test:\n test_case(test)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 22873