#pragma warning(disable:4786)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>

using namespace std;

typedef vector<int> vint;

int pos(int a,int b)    ////compute the number on the point (a,b);
{
	int result=0;
	for (int i=1;i<=a;i++)
	{
		result+=i;
	}
	return(result+b+1);
}

bool solution(vector<vint>& board,int n,vint& result)///put the result in the "result";
{
	int i,j,k,sum=0;
	for(j=0;j<n;j++)for( k=0;k<=j;k++)
	{
		if(board[j][k]) sum+=1;////compute the number of leftover
	}
	if(sum==1) return(1);//only one left;(reached the lower bound) add &&board.at(0) fix the point
	for(i=0;i<n;i++)        
	for(j=0;j<=i;j++)
	{
		if(board[i][j]==1)////if point(i,j) is not blank,
		{
			if(j>=2&&board[i][j-1]==1&&board[i][j-2]==0)
			{
				board[i][j]=0;board[i][j-1]=0;board[i][j-2]=1;
				if(solution(board,n, result))
				{result.push_back(pos(i,j-2));result.push_back(pos(i,j));return 1;}
				else
				{
					board[i][j]=1;board[i][j-1]=1;board[i][j-2]=0;
				}
			}if(i>=2&&j>=2&&board[i-1][j-1]==1&&board[i-2][j-2]==0)
			{
				board[i][j]=0;board[i-1][j-1]=0;board[i-2][j-2]=1;
				if(solution(board,n, result))
				{result.push_back(pos(i-2,j-2));result.push_back(pos(i,j));return 1;}
				else
				{
					board[i][j]=1;board[i-1][j-1]=1;board[i-2][j-2]=0;
				}
			}if(i>=2&&board[i-1][j]==1&&board[i-2][j]==0)
			{
				board[i][j]=0;board[i-1][j]=0;board[i-2][j]=1;
				if(solution(board,n, result))
				{result.push_back(pos(i-2,j));result.push_back(pos(i,j));return 1;}
				else
				{
					board[i][j]=1;board[i-1][j]=1;board[i-2][j]=0;
				}
			}if(j+2<=i&&board[i][j+1]==1&&board[i][j+2]==0)
			{
				board[i][j]=0;board[i][j+1]=0;board[i][j+2]=1;
				if(solution(board,n, result))
				{result.push_back(pos(i,j+2));result.push_back(pos(i,j));return 1;}
				else
				{
					board[i][j]=1;board[i][j+1]=1;board[i][j+2]=0;
				}
			}if(i+2<n&&board[i+1][j+1]==1&&board[i+2][j+2]==0)
			{
				board[i][j]=0;board[i+1][j+1]=0;board[i+2][j+2]=1;
				if(solution(board,n, result))
				{result.push_back(pos(i+2,j+2));result.push_back(pos(i,j));return 1;}
				else
				{
					board[i][j]=1;board[i+1][j+1]=1;board[i+2][j+2]=0;
				}
			}if(i+2<n&&board[i+1][j]==1&&board[i+2][j]==0)
			{
				board[i][j]=0;board[i+1][j]=0;board[i+2][j]=1;
				if(solution(board,n, result))
				{result.push_back(pos(i+2,j));result.push_back(pos(i,j));return 1;}
				else
				{
					board[i][j]=1;board[i+1][j]=1;board[i+2][j]=0;
				}
			}
		}
		
	}
	return 0;
}

int main()
{
	int i,j,n=1;
	vector<vint> board;
	vint record;
	ofstream ii("answer");
	for(;;)
	{/////////////begin the loop
	board.resize(n);for(i=0;i<n;i++)board[i].clear();

		cout<<"please input the number of board size:0 to quit\n";
	
	
	cin>>n;
	if(n==0)break;/////skip the loop

	record.clear();
	ii<<"size is "<<n;
	board.resize(n);
	board[0].clear();
	board[0].push_back(0);
	for(j=1;j<n;j++)
		{
		board[j].clear();
		for(i=0;i<=j;i++)
		board[j].push_back(1);
	}
	if(solution(board,n,record))
	{
		cout<<endl;
		while(!record.empty())
		{
			cout<<record.back();
			ii<<record.back();
			cout<<" to ";
			ii<<" to ";
			record.pop_back();
			cout<<record.back();
			ii<<record.back();
			record.pop_back();
			ii<<endl;
			cout<<endl;
		}
	}
	else {cout<<"\n Sorry,there is no solution!\n\n\n";
		ii<<"\n no solution!\n\n\n";}
	}//////////end the loop
	return 0;
}