#include <iostream>
using namespace std;
#define MAX_K 65
char np[MAX_K];
int b[MAX_K];
int T,K;
long long int N;
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&K); scanf("%s",np); scanf("%lld",&N);
		for(int i=K-1;i>=0;i--)
		{
			if(abs(N)%2)
			{
				b[i]=1;
				if(np[i]=='n')
					N+=1;
				else
					N-=1;
			}else{
				b[i]=0;
			}
			N/=2;
		}
		if(N)
			printf("Impossible\n");
		else
		{
		for(int i=0;i<=K-1;i++)
			printf("%d",b[i]);
		printf("\n");
		}
	}
	return 0;
}