#pragma warning(disable:4786)
#include <iostream>
#include <vector>
#include <string>
#include <deque>
using namespace std;

typedef vector<int> vb;
typedef deque<int> di;
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 recur(vb lbs,int n,di& dec)///put the result in the dec;
{
	int i,j,k,sum=0;
	for(j=0;j<n;j++)for( k=0;k<=j;k++)
	{
		if(lbs[j*n+k]==1) sum+=1;////compute the number of leftover
	}
	if(sum==1) return(1);//only one left;(reached the lower bound) add &&lbs[0] fix the point
	for(i=0;i<n;i++)        
	for(j=0;j<=i;j++)
	{
		if(lbs[i*n+j]==0)////if point(i,j) is blank,
		{
			if(j>=2&&lbs[i*n+j-1]==1&&lbs[i*n+j-2]==1)
			{
				lbs[i*n+j]=1;lbs[i*n+j-1]=0;lbs[i*n+j-2]=0;
				if(recur(lbs,n, dec))
				{dec.push_back(pos(i,j));dec.push_back(pos(i,j-2));return 1;}
				else
				{
					lbs[i*n+j]=0;lbs[i*n+j-1]=1;lbs[i*n+j-2]=1;
				}
			}
			if(j>=2&&i>=2&&lbs[(i-1)*n+j-1]==1&&lbs[(i-2)*n+j-2]==1)
			{
				lbs[i*n+j]=1;lbs[(i-1)*n+j-1]=0;lbs[(i-2)*n+j-2]=0;
				if(recur(lbs,n,dec))
				{dec.push_back(pos(i,j));dec.push_back(pos(i-2,j-2));return 1;}
				else
				{
					lbs[i*n+j]=0;lbs[(i-1)*n+j-1]=1;lbs[(i-2)*n+j-2]=1;
				}

			}
			if(i>=2&&j+2<=i&&lbs[(i-1)*n+j]==1&&lbs[(i-2)*n+j]==1)
			{
				lbs[i*n+j]=1;lbs[(i-1)*n+j]=0;lbs[(i-2)*n+j]=0;
				if(recur(lbs,n,dec))
				{dec.push_back(pos(i,j));dec.push_back(pos(i-2,j));return 1;}
				else
				{
					lbs[i*n+j]=0;lbs[(i-1)*n+j]=1;lbs[(i-2)*n+j]=1;
				}

			}
			if(j+2<=i&&lbs[i*n+j+1]==1&&lbs[i*n+j+2]==1)
			{
				lbs[i*n+j]=1;lbs[i*n+j+1]=0;lbs[i*n+j+2]=0;
				if(recur(lbs,n,dec))
				{dec.push_back(pos(i,j));dec.push_back(pos(i,j+2));return 1;}
				else
				{
					lbs[i*n+j]=0;lbs[i*n+j+1]=1;lbs[i*n+j+2]=1;
				}

			}
			if(i+2<n&&lbs[(i+1)*n+j+1]==1&&lbs[(i+2)*n+j+2]==1)
			{
				lbs[i*n+j]=1;lbs[(i+1)*n+j+1]=0;lbs[(i+2)*n+j+2]=0;
				if(recur(lbs,n,dec))
				{dec.push_back(pos(i,j));dec.push_back(pos(i+2,j+2));return 1;}
				else
				{
					lbs[i*n+j]=0;lbs[(i+1)*n+j+1]=1;lbs[(i+2)*n+j+2]=1;
				}

			}
			if(i+2<n&&lbs[(i+1)*n+j]==1&&lbs[(i+2)*n+j]==1)
			{
				lbs[i*n+j]=1;lbs[(i+1)*n+j]=0;lbs[(i+2)*n+j]=0;
				if(recur(lbs,n,dec))
				{dec.push_back(pos(i,j));dec.push_back(pos(i+2,j));return 1;}
				else
				{
					lbs[i*n+j]=0;lbs[(i+1)*n+j]=1;lbs[(i+2)*n+j]=1;
				}

			}
		}
		
	}
	return 0;
}

int main()
{
	int j,n;
	vector<int> board;
	di record;
	for(;;)
	{/////////////begin the loop
	cout<<"please input the number of board size:0 to quit\n";
	cin>>n;
	if(n==0)break;/////skip the loop
	board.clear();record.clear();
	board.push_back(0);
	for(j=1;j<n*n;j++)board.push_back(1);
	if(recur(board,n,record))
	{
		cout<<endl;
		while(!record.empty())
		{
			cout<<record.back();
			cout<<" to ";
			record.pop_back();
			cout<<record.back();
			record.pop_back();
			cout<<endl;
		}

	}
	else cout<<"\n Sorry,there is no solution!\n\n\n";
	}//////////end the loop
	return 0;
}