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: interview

Starter code:

Solutions:
# cook your dish here
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)

# cook your dish here
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)

# cook your dish here
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):]
   #print(l1)
  str3+=l1[0]
 print(str3)
  
 t=t-1

# cook your dish here
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)
  


# cook your dish here
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

# cook your dish here
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)


# cook your dish here
for i in range(int(input())):
 n = int(input())
 a = str(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'}

 ans = ''
 for i in range(0,len(a),4):
  x = a[i:i+4]
  ans+=(d.get(x))
 print(ans)

# cook your code here
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)

# cook your dish here
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)

# cook your dish here  
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


# cook your dish here
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

# cook your dish here
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)
  



# cook your dish here
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)

# cook your dish here
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('')

for _ 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)


# cook your dish her
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