#include <bits/stdc++.h>
using namespace std;

#define   f(i,n) 			for(int i=0;i<(n);i++)
#define   ff(i,n)           for(int i=1;i<=(n);i++)
#define   m0(X) 			memset((X), 0, sizeof((X)))
#define   m1(X) 			memset((X), -1, sizeof((X)))
#define   pb(x) 			push_back(x)
#define   ay                100005
#define   rt                return 0
#define   sr(x,n)           sort(x+1,x+n+1)
#define   sv(v)             sort(v.begin(),v.end())
#define   fs                first
#define   sc                second
#define   cs(a)				cout<<"Case "<<css<<": "<<a<<"\n";
#define   pf(a)				printf("%c",a)
#define   sf(a)				scanf("%d",&a)

typedef long long ll;
typedef unsigned long long ull;
const ll mod=1000*1000*1000+7;
const  double pi = acos(-1.0);
const  double eps= 1e-9;
const ll inf = 1e18;

int toint(string s){int sm;stringstream ss(s);ss>>sm;return sm;}
ll tolint(string s){long long  sm;stringstream ss(s);ss>>sm;return sm;}
int cnt=0;
struct{
	int i;int j;
}goal[20];

int puz[5][5],path[55],mx;

int inversion(){
	int sum=0;
	int r,c;
	for(int i=1;i<=4;i++)
	for(int j=1;j<=4;j++){
		if(puz[i][j]==0){
			r=i;
			continue;
		}
		ff(p,4)ff(q,4){
			if(puz[p][q]==0)continue;
			if(p>i||(p==i&&q>j)){
				if(puz[i][j]>puz[p][q])sum++;
			}
		}
	}
	if(!((r%2==0&&sum%2==0)||(r%2!=0&&sum%2!=0))){
			return 0;
		}
		return 1;
}

int calculate(){
	//cnt++;
	int sum=0,a,m=0,ex=0;
	ff(i,4)ff(j,4){

		a=(abs(goal[puz[i][j]].i-i)+abs(goal[puz[i][j]].j-j));
		m=max(a,m);
		sum+=a;
	}

	sum+=ex/2;
	//cout<<ex<<" "<<sum<<"\n";
	return max(sum-m,1);
}

int hu(){

	int p=1;
	ff(i,4)ff(j,4){
		if(i==4&&j==4){
			 return 0;
		}
		if(puz[i][j]!=p)return calculate();
		p++;
	}
	return 0;
}

int minval=mod;
bool f=1;
int dfs(int p,int prev,int r,int c){
	int h=hu();
	int heuristic=p+h-1;

	//cout<<hu()<<" ";
	minval=min(minval,heuristic);
	if(heuristic>mx){
		return mod;
	}
	if(h==0){
		f=0;return p-1;
	}
	int mn=mod;

	if(prev!=1&&r+1<=4&&f){
		swap(puz[r][c],puz[r+1][c]);
		path[p]=-1;
		mn=min(mn,dfs(p+1,-1,r+1,c));
		swap(puz[r][c],puz[r+1][c]);
	}

	if(prev!=-2&&c-1>0&&f){
		swap(puz[r][c],puz[r][c-1]);
		path[p]=2;
		mn=min(mn,dfs(p+1,2,r,c-1));
		swap(puz[r][c],puz[r][c-1]);
	}
	if(prev!=2&&c+1<=4&&f){
		swap(puz[r][c],puz[r][c+1]);
		path[p]=-2;
		mn=min(mn,dfs(p+1,-2,r,c+1));
		swap(puz[r][c],puz[r][c+1]);
	}
	if(prev!=-1&&r-1>0&&f){
		swap(puz[r][c],puz[r-1][c]);
		path[p]=1;
		mn=min(mn,dfs(p+1,1,r-1,c));
		swap(puz[r][c],puz[r-1][c]);
	}
	return mn;
}



int e;

string s;
int main()
{
    int p=1;
    ff(i,4)ff(j,4){
    	goal[p].i=i;
    	goal[p++].j=j;
	}
	goal[0].i=goal[0].j=4;

    int n,r,c;
    sf(n);
    ff(z,n){

    	ff(i,4)ff(j,4){
    		sf(puz[i][j]);
    		if(puz[i][j]==0){
    			r=i,c=j;
			}
		}
		mx=1;
		int ans=mod;
		int x=inversion();
		if(x==0){
			printf("Case %d: This puzzle is not solvable.\n",z);
			continue;
		}
		while(mx<=35){
			e=dfs(1,0,r,c);
			if(e<mod){
				ans=e;break;
			}
			mx++;
			mx=max(mx,minval);
		}

		if(f==1)printf("Case %d: This puzzle is not solvable.\n",z);

		else {
			printf("Case %d: ",z);
			for(int i=1;i<=ans;i++){
				if(path[i]==1)printf("%c",'U');
				else if(path[i]==-1)printf("%c",'D');
				else if(path[i]==2)printf("%c",'L');
				else if(path[i]==-2)printf("%c",'R');
			}
			printf("\n");

		}

		f=1;
		minval=mod;
	}
//cout<<cnt;
}