#include <cstdio>
#include <cstring>
#include <memory.h>
using namespace std;

int sn,n,pn,temp,pos[100001],dad[100001];
char que[100001][20];
bool flag;

bool succ(int head)
{
	int i,c;
	c=0;
	for (i=0;i<n;i++)
	{
		if (que[head][i]=='a')
			c++;
		else if (que[head][i]=='b')
			return(false);
		if (c==sn)
			break;
	}
	return(true);
}

bool dup(int head)
{
	int i;
	for (i=0;i<head;i++)
		if (pos[head]==pos[i])
			if (strcmp(que[head],que[i])==0)
				return(true);
	return(false);
}

void printans(int pos,int deep)
{
	int i;
	if (pos!=0)
		printans(dad[pos],deep+1);
	else
		temp=deep;
	printf("%d ",temp-deep);
	for (i=0;i<n;i++)
		printf("%c",que[pos][i]);
	printf("\n");
}

int main(void)
{
	freopen("balls.in","r",stdin);
	freopen("balls.out","w",stdout);
	int i,j,jj,k,l,tail,head,pos1,pos2,len;
	char ch1,ch2;
	bool flag2;
	scanf("%d\n",&k);
	for (i=0;i<k;i++)
	{
		tail=0;
		head=0;
		memset(que,0,sizeof(que));
		memset(dad,0,sizeof(dad));
		memset(pos,0,sizeof(pos));
		scanf("%d\n%[^\n]\n",&n,&que[0]);
		flag=false;
		sn=n-1;
		n+=n;
		pn=n-1;
		flag2=false;
		len=strlen(que[0]);
		for (j=len-1;j>=0;j--)
		{
			if (que[0][j]!='a'&&que[0][j]!='b')
				flag2=true;
		}
		if (!flag2)
		{
			que[0][len+1]='\0';
			que[0][len]=' ';
		}
		que[0][n]='\0';
		len=strlen(que[0]);
		for (j=len-1;j>=0;j--)
			if (que[0][j]!='a'&&que[0][j]!='b')
			{
				for (l=pn;l>j;l--)
					que[0][l]=que[0][l-1];
				pos[0]=j;
				que[0][j]=' ';
				que[0][j+1]=' ';
				break;
			}
		if (succ(head))
		{
			printans(head,0);
			flag=true;
		}
		while (!flag&&tail<=head||head>=99900)
		{
			pos1=pos[tail]-1;
			pos2=pos[tail]+1;
			for (j=0;!flag&&j<pn;j++)
			{
				if (j==pos[tail]||j==pos1||j==pos2)
					continue;
				head++;
				jj=j+1;
				dad[head]=tail;
				pos[head]=j;
				for (l=0;l<n;l++)
					que[head][l]=que[tail][l];
				ch1=que[head][j];
				ch2=que[head][jj];
				que[head][j]=' ';
				que[head][jj]=' ';
				que[head][pos[tail]]=ch1;
				que[head][pos[tail]+1]=ch2;
				if (succ(head))
				{
					printans(head,0);
					flag=true;
				}
				if (dup(head))
					head--;
			}
			tail++;
		}
		if (!flag)
			printf("NO SOLUTION\n");
	}
	return(0);
}