#include<stdio.h>
#include<math.h>
#include<string.h>
char s[100005];
char cs(int a){
	switch(a){
		case 10: return 'A';
		case 11: return 'B';
		case 12: return 'C';
		case 13: return 'D';
		case 14: return 'E';
		case 15: return 'F';
		default: return a+'0';
	}
}
int main(){
	int t,n;
	scanf("%d",&t);
	while(t--){
		int i,k,l,m,d;
		scanf("%d",&n);
		scanf("%s",&s);
		if(n==2) printf("%s",s);
		else{
		l=0;m=strlen(s);
		if(n==4){
			k=2;
		}else if(n==8) k=3;
		else if(n==16) k=4;
		int du=m%k;
		if(du>0){
			for(i=0;i<du;i++)
			l=l*2+s[i]-'0';
			printf("%c",cs(l));
		}
		l=0;
		for(i=du;i<m;i++){
			l=l*2+s[i]-48;
			if((du > 0 && i%k==du-1)||(du==0 && i%k==k-1)){
				printf("%c",cs(l));
				l=0;
			}}
		}printf("\n");
	}return 0;
}