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$.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
def decode(L, S):
	str_2 = ''
	lst = []
	for i in range(L // 4):
		str_1 = 'abcdefghijklmnop'
		S_1 = S[i * 4:4 * (i + 1)]
		for j in range(4):
			if S_1[j] == '1':
				str_1 = str_1[len(str_1) // 2:len(str_1)]
			else:
				str_1 = str_1[0:len(str_1) // 2]
		str_2 = str_2 + str_1
	print(str_2)
T = int(input())
for i in range(T):
	L = int(input())
	S = input()
	decode(L, S)


testcases = int(input())
alphabet = 'aiemckgobjfndlhp'
for testcase in range(testcases):
	length = int(input())
	code = input()
	string = ''
	for byte in range(0, length, 4):
		letter = code[:4]
		num = int(code[3]) * 8 + int(code[2]) * 4 + int(code[1]) * 2 + int(code[0])
		string += alphabet[num]
		code = code[4:]
	print(string)


t = int(input())
for e in range(t):
	n = int(input())
	s = input()
	ans = ''
	for i in range(0, n, 4):
		s2 = s[i] + s[i + 1] + s[i + 2] + s[i + 3]
		l = [chr(q) for q in range(97, 113)]
		for z in s2:
			if z == '0':
				l = l[0:int(len(l) / 2)]
			else:
				l = l[int(len(l) / 2):]
		ans = ans + l[0]
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	str1 = input()
	str3 = ''
	for i in range(0, n, 4):
		str2 = str1[i] + str1[i + 1] + str1[i + 2] + str1[i + 3]
		l1 = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p']
		for j in str2:
			if j == '0':
				l1 = l1[:int(len(l1) / 2)]
			else:
				l1 = l1[int(len(l1) / 2):]
		str3 += l1[0]
	print(str3)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	s = input()
	d = {'0000': 'a', '0001': 'b', '0010': 'c', '0011': 'd', '0100': 'e', '0101': 'f', '0110': 'g', '0111': 'h', '1000': 'i', '1001': 'j', '1010': 'k', '1011': 'l', '1100': 'm', '1101': 'n', '1110': 'o', '1111': 'p'}
	a = ''
	for i in range(0, n, 4):
		x = s[i:i + 4]
		a += d.get(x)
	print(a)


def find(n, i):
	if i == '0':
		return n // 2
	else:
		return n
alphabets = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p']
test = int(input())
while test != 0:
	bits = int(input())
	li = list(input())
	k = 0
	while bits >= 4:
		t = 16
		s = ''
		for i in range(k, k + 4):
			s = s + li[i]
		bits = bits - 4
		k = k + 4
		s = int(s, 2)
		print(alphabets[s], end='')
	print()
	test = test - 1


for _ in range(int(input())):
	n = int(input())
	lst = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p']
	f = lst
	o = ''
	fo = ''
	s = input()
	for i in range(n + 1):
		if i % 4 == 0:
			fo += o
			f = lst
		if i == n:
			break
		if int(s[i]) == 0:
			f = f[:len(f) // 2]
			o = f[0]
		elif int(s[i]) == 1:
			f = f[len(f) // 2:]
			o = f[0]
	print(fo)


zz = int(input(''))
for j in range(zz):
	xx = int(input(''))
	x = list(input(''))
	kk = 0
	sos = ''
	for i in range(xx, 0, -4):
		t = 3
		c = 0
		for k in range(4):
			c = c + int(x[kk]) * 2 ** t
			kk = kk + 1
			t = t - 1
		sos = sos + chr(c + 97)
	print(sos)


map_dict = {'0000': 'a', '0001': 'b', '0010': 'c', '0011': 'd', '0100': 'e', '0101': 'f', '0110': 'g', '0111': 'h', '1000': 'i', '1001': 'j', '1010': 'k', '1011': 'l', '1100': 'm', '1101': 'n', '1110': 'o', '1111': 'p'}

def decode_it(s):
	l = len(s)
	ch_list = []
	for i in range(0, l, 4):
		ind = s[i:i + 4]
		x = map_dict[ind]
		ch_list.append(x)
	return ''.join(ch_list)
T = int(input())
while T > 0:
	l = int(input())
	s = input()
	print(decode_it(s))
	T -= 1


d = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p']
for t in range(int(input())):
	n = int(input())
	s = input()
	string = ''
	for i in range(0, n - 3, 4):
		string += d[int(s[i:i + 4], 2)]
	print(string)


t = int(input())
while t:
	k = int(input())
	s = input()
	n = 4
	l = [s[i:i + n] for i in range(0, k, n)]
	li = []
	for i in l:
		li.append(chr(int(i, 2) + 97))
	print(''.join((i for i in li)))
	t -= 1


def find_string(k):
	f = 'abcdefghijklmnop'
	for i in range(0, len(k)):
		if k[i] == '1':
			f = f[len(f) // 2:]
		elif k[i] == '0':
			f = f[:len(f) // 2]
	return f
t = int(input())
while t:
	o = int(input())
	k = input()
	res = ''
	j = 0
	while j + 3 in range(len(k)):
		res = res + find_string(k[j:j + 4])
		j = j + 4
	print(res)
	t = t - 1


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	arr = []
	for i in range(97, 113):
		arr.append(chr(i))
	i = 0
	while i < n:
		k = 0
		l = 15
		while k < l:
			m = (k + l) // 2
			if k >= l:
				break
			if s[i] == '0':
				l = m
			elif s[i] == '1':
				k = m + 1
			i = i + 1
		print(arr[k], end='')
	print()
	t = t - 1


def division(x, s):
	l = []
	for i in range(0, s, 4):
		l.append(x[i:i + 4])
	return l
t = int(input())
for i in range(t):
	size = int(input())
	x = input()
	s = division(x, size)
	string = ''
	for i in s:
		sum1 = 0
		for j in range(4):
			sum1 += 2 ** (3 - j) * int(i[j])
		sum1 += 97
		string += chr(sum1)
	print(string)


for _ in range(int(input())):
	l = int(input())
	s = input()
	string = 'abcdefghijklmnop'
	decode = ''
	for b in range(0, l, 4):
		string = 'abcdefghijklmnop'
		for a in range(b, b + 4):
			if s[a] == '0':
				n = len(string) // 2
				string = string[0:n]
			elif s[a] == '1':
				n = len(string)
				string = string[n // 2:n]
		decode = decode + string
	print(decode)


for i in range(int(input())):
	N = int(input())
	S = input()
	for i in range(0, N, 4):
		print(chr(97 + int(S[i:i + 4], 2)), end='')
	print('')


import sys
import math

class Test:
	N = 0
	S = []

	def __init__(self):
		tmp = input().split()
		self.N = int(tmp[0])
		self.S = [int(i) for i in input()]

class Input:
	T = 0
	test = []

	def __init__(self):
		self.T = int(input())
		for i in range(0, self.T):
			self.test.append(Test())
letter = []
letter.append([])
letter.append([])
letter[0].append([])
letter[0].append([])
letter[1].append([])
letter[1].append([])
letter[0][0].append([])
letter[0][0].append([])
letter[0][1].append([])
letter[0][1].append([])
letter[1][0].append([])
letter[1][0].append([])
letter[1][1].append([])
letter[1][1].append([])
letter[0][0][0].append('a')
letter[0][0][0].append('b')
letter[0][0][1].append('c')
letter[0][0][1].append('d')
letter[0][1][0].append('e')
letter[0][1][0].append('f')
letter[0][1][1].append('g')
letter[0][1][1].append('h')
letter[1][0][0].append('i')
letter[1][0][0].append('j')
letter[1][0][1].append('k')
letter[1][0][1].append('l')
letter[1][1][0].append('m')
letter[1][1][0].append('n')
letter[1][1][1].append('o')
letter[1][1][1].append('p')

def getletter(i, j, k, l):
	return letter[i][j][k][l]

def test_case(t: Test):
	sum = 0
	i = 0
	string = ''
	while i + 3 < len(t.S):
		string += getletter(t.S[i], t.S[i + 1], t.S[i + 2], t.S[i + 3])
		i += 4
	print(string)
inp = Input()
for test in inp.test:
	test_case(test)


t = int(input())
while t:
	a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p']
	n = int(input())
	s = input()
	res = ''
	for i in range(0, len(s), 4):
		res = res + a[int(s[i:i + 4], 2)]
	print(res)
	t -= 1