10085

#include <iostream>
#include <string.h>
#include <string>
#include <vector>

#define MX 1000003

using namespace std;

int kase = 1;
int in[9];
int visit[MX];
int next[MX];
int par[MX];
char val[MX];
int num[MX][9];
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
vector<int> vb[MX];
string s;

int GetHash(int *arr)
{
	int h=0;
	for(int i=0;i<9;i++)
	{
		h=h*10+arr[i];
	}

	h=h%MX;
	return h;
}


bool isNew(int *arr,int pos)
{
	int h=GetHash(arr);

	for(int i=0;i<vb[h].size();i++)
	{
		if(memcmp(arr,num[i]],sizeof(arr))==0)
		return false;
	}

	vb[h].push_back(pos);

	return true;
}

//isNew() in a different way but same algo
/*
bool isNew(int *arr,int pos)
{
	int h=GetHash(arr);
	int u = visit[h];

	while(u)
	{
		if(memcmp(num[u],arr,sizeof(num[u]))==0)
		return false;
		u = next[u];
	}

	next[pos] = visit[h];
	visit[h] = pos;

	return true;
}
*/
int path(int n)
{
	if(par[n]!=-1)
	{
		s.append(1u,val[n]);
		path(par[n]);
	}
	else
	return 0;
}

void bfs()
{
	int front =1,rear=0;
	memcpy(num[0],in,sizeof(in));
	int b[9];
	par[0]=-1;
	while(front>rear)
	{
		int a[9];
		int zero;
		memcpy(a,num[rear],sizeof(a));
		for(int i=0;i<9;i++)
		{
			if(a[i]==0)
			{
				zero=i;
				break;
			}
		}

		int dx =zero/3;
		int dy =zero%3;

		for(int i=0;i<4;i++)
		{
			int x = dir[i][0]+dx;
			int y = dir[i][1]+dy;
			if(x>=0&&x<3&&y>=0&&y<3)
			{
				int m = 3*x+y;
				memcpy(b,a,sizeof(a));
				b[zero] = a[m];
				b[m] = a[zero];
				memcpy(num[front],b,sizeof(b));
				if(isNew(b,front))
				{
					par[front]=rear;
					if(i==0)
						val[front]='D';
					else if(i==1)
						val[front]='R';
					else if(i==2)
						val[front]='U';
					else if(i==3)
						val[front]='L';

					front++;
				}
			}
		}
		rear++;
	}
	front--;
	cout<<"Puzzle #"<<kase++<<"\n";
	for(int i=0;i<9;i++)
	{
		cout<<num[front][i]<<((i%3==2)?"\n":" ");
	}
	s="";
	path(front);

	for(int i=s.size()-1;i>=0;i--)
		cout<<s[i];
	cout<<"\n\n";
}



int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		for(int i=0;i<9;i++)
		{
			cin>>in[i];
		}
		//memset(visit,0,sizeof(visit));
		//memset(next,0,sizeof(next));
		for(int i=0;i<MX;i++)
		{
			vb[i].clear();
			visit[i]=0;
			par[i]=0;
		}
		bfs();
	}
	return 0;
}