分球

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

在一个装满财宝的屋子里,有2N个盒子排成一排。除了两个相邻的空盒外,其余的每个盒子里都装有一个金球或者一个银球,总共有N-1个金球和N-1个银球。如图1所示为一个N=5时的例子,G表示金球,S表示银球。 



 任意两个相邻的非空的盒子里的球可以移动到两个相邻的空盒中,移动不能改变这两个球的排列顺序。写一个程序,用最少的移动次数把所有的金球都移动到所有的银球的左边。

Input

输入数据包含多组。第一行为K,表示数据的总数。

每组数据的第一行是N(3<=N<=7),第二行是2N个盒子的初始状态。金球用a表示,银球用b表示,空盒用空格表示。每两组相邻数据用空行隔开。

Output

对于每一组数据,若无解则输出一行NO SOLUTION,若有解,输出一组状态来表示移动的序列,每个状态占一行。每行输出到此状态的移动的步数,紧接着是一个空格,然后是此时的状态。

初始状态为第0步,每组数据都要先输出初始状态。

如有多种最少移动次数方案,只需输出任意一种。相邻的两组数据用一个空行隔开。

Sample Input

2
4
  aaabbb

4
a  aabbb

Sample Output

0   aaabbb

0 a  aabbb

Hint

Source