#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define LLU unsigned long long
using namespace std;
struct status {
char board[4][4];
int ix, iy;
} init;
int pos[16][2], mxdep;
int dir[4][2] = {{0,-1},{-1,0},{1,0},{0,1}};/*u,l,r,d*/
char dirc[4] = {'L', 'U', 'D', 'R'}, path[100];
int solved;
bool solvable() {
int sum = 0, row, i, j;
for(i = 0; i < 16; i++) {
if(init.board[i/4][i%4] == 0) {
row = i/4 + 1;
continue;
}
for(j = i+1; j < 16; j++) {
if(init.board[j/4][j%4] < init.board[i/4][i%4]) {
if(init.board[j/4][j%4])
sum++;
}
}
}
return 1-(sum+row)%2;
}
int H() {
static int i, j, sum, num;
sum = 0;
for(i = 0; i < 4; i++) {
for(j = 0; j < 4; j++) {
num = init.board[i][j];
if(num == 0)
continue;
sum += abs(i-pos[num][0]) + abs(j-pos[num][1]);
}
}
return sum;
}
int Htable[4][4][16];
int IDA(int dep, int hv, int prestep) {
if(hv == 0) {
solved = dep;
path[dep] = '\0';
puts(path);
return dep;
}
if(dep + 5*hv/3 > mxdep) {
return dep + 5*hv/3;
}
int i, tx, ty, x = init.ix, y = init.iy;
int submxdep = 0xfff, val = 0xfff, shv;
for(i = 0; i < 4; i++) {
if(i + prestep == 3) continue;
tx = x + dir[i][0], ty = y + dir[i][1];
if(tx < 0 || ty < 0 || tx > 3 || ty > 3)
continue;
shv = hv;
shv -= Htable[tx][ty][init.board[tx][ty]];
shv += Htable[x][y][init.board[tx][ty]];
init.ix = tx, init.iy = ty;
swap(init.board[x][y], init.board[tx][ty]);
path[dep] = dirc[i];
val = IDA(dep+1, shv, i);
swap(init.board[x][y], init.board[tx][ty]);
init.ix = x, init.iy = y;
if(solved) return solved;
submxdep = min(submxdep, val);
}
return submxdep;
}
int main() {
int test, i, j, k, initH;
int cases = 0;
for(i = 0, k = 0; i < 4; i++)
for(j = 0; j < 4; j++)
pos[++k][0] = i, pos[k][1] = j;
for(i = 0; i < 4; i++)
for(j = 0; j < 4; j++)
for(k = 1; k < 16; k++)
Htable[i][j][k] = abs(i - pos[k][0]) + abs(j - pos[k][1]);
scanf("%d", &test);
while(test--) {
cases++;
for(i = 0; i < 4; i++) {
for(j = 0; j < 4; j++) {
scanf("%d", &k);
init.board[i][j] = k;
if(init.board[i][j] == 0) {
init.ix = i, init.iy = j;
}
}
}
if(solvable()) {
solved = 0, initH = mxdep = H();
if(!mxdep) {
puts("");
continue;
}
while(solved == 0)
mxdep = IDA(0, initH, -1);
//printf("%d\n", solved);
}else {
puts("This puzzle is not solvable.");
}
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2RlZmluZSBMTFUgdW5zaWduZWQgbG9uZyBsb25nCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnN0cnVjdCBzdGF0dXMgewogICAgY2hhciBib2FyZFs0XVs0XTsKICAgIGludCBpeCwgaXk7Cn0gaW5pdDsKaW50IHBvc1sxNl1bMl0sIG14ZGVwOwppbnQgZGlyWzRdWzJdID0ge3swLC0xfSx7LTEsMH0sezEsMH0sezAsMX19Oy8qdSxsLHIsZCovCmNoYXIgZGlyY1s0XSA9IHsnTCcsICdVJywgJ0QnLCAnUid9LCBwYXRoWzEwMF07CmludCBzb2x2ZWQ7CmJvb2wgc29sdmFibGUoKSB7CiAgICBpbnQgc3VtID0gMCwgcm93LCBpLCBqOwogICAgZm9yKGkgPSAwOyBpIDwgMTY7IGkrKykgewogICAgICAgIGlmKGluaXQuYm9hcmRbaS80XVtpJTRdID09IDApIHsKICAgICAgICAgICAgcm93ID0gaS80ICsgMTsKICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgfQogICAgICAgIGZvcihqID0gaSsxOyBqIDwgMTY7IGorKykgewogICAgICAgICAgICBpZihpbml0LmJvYXJkW2ovNF1baiU0XSA8IGluaXQuYm9hcmRbaS80XVtpJTRdKSB7CiAgICAgICAgICAgICAgICBpZihpbml0LmJvYXJkW2ovNF1baiU0XSkKICAgICAgICAgICAgICAgICAgICBzdW0rKzsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIHJldHVybiAxLShzdW0rcm93KSUyOwp9CmludCBIKCkgewogICAgc3RhdGljIGludCBpLCBqLCBzdW0sIG51bTsKICAgIHN1bSA9IDA7CiAgICBmb3IoaSA9IDA7IGkgPCA0OyBpKyspIHsKICAgICAgICBmb3IoaiA9IDA7IGogPCA0OyBqKyspIHsKICAgICAgICAgICAgbnVtID0gaW5pdC5ib2FyZFtpXVtqXTsKICAgICAgICAgICAgaWYobnVtID09IDApCiAgICAgICAgICAgICAgICBjb250aW51ZTsKICAgICAgICAgICAgc3VtICs9IGFicyhpLXBvc1tudW1dWzBdKSArIGFicyhqLXBvc1tudW1dWzFdKTsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gc3VtOwp9CmludCBIdGFibGVbNF1bNF1bMTZdOwppbnQgSURBKGludCBkZXAsIGludCBodiwgaW50IHByZXN0ZXApIHsKICAgIGlmKGh2ID09IDApIHsKICAgICAgICBzb2x2ZWQgPSBkZXA7CiAgICAgICAgcGF0aFtkZXBdID0gJ1wwJzsKICAgICAgICBwdXRzKHBhdGgpOwogICAgICAgIHJldHVybiBkZXA7CiAgICB9CiAgICBpZihkZXAgKyA1Kmh2LzMgPiBteGRlcCkgewogICAgICAgIHJldHVybiBkZXAgKyA1Kmh2LzM7CiAgICB9CiAgICBpbnQgaSwgdHgsIHR5LCB4ID0gaW5pdC5peCwgeSA9IGluaXQuaXk7CiAgICBpbnQgc3VibXhkZXAgPSAweGZmZiwgdmFsID0gMHhmZmYsIHNodjsKCiAgICBmb3IoaSA9IDA7IGkgPCA0OyBpKyspIHsKICAgICAgICBpZihpICsgcHJlc3RlcCA9PSAzKSAgICBjb250aW51ZTsKICAgICAgICB0eCA9IHggKyBkaXJbaV1bMF0sIHR5ID0geSArIGRpcltpXVsxXTsKICAgICAgICBpZih0eCA8IDAgfHwgdHkgPCAwIHx8IHR4ID4gMyB8fCB0eSA+IDMpCiAgICAgICAgICAgIGNvbnRpbnVlOwoKICAgICAgICBzaHYgPSBodjsKICAgICAgICBzaHYgLT0gSHRhYmxlW3R4XVt0eV1baW5pdC5ib2FyZFt0eF1bdHldXTsKICAgICAgICBzaHYgKz0gSHRhYmxlW3hdW3ldW2luaXQuYm9hcmRbdHhdW3R5XV07CiAgICAgICAgaW5pdC5peCA9IHR4LCBpbml0Lml5ID0gdHk7CiAgICAgICAgc3dhcChpbml0LmJvYXJkW3hdW3ldLCBpbml0LmJvYXJkW3R4XVt0eV0pOwoKICAgICAgICBwYXRoW2RlcF0gPSBkaXJjW2ldOwogICAgICAgIHZhbCA9IElEQShkZXArMSwgc2h2LCBpKTsKCiAgICAgICAgc3dhcChpbml0LmJvYXJkW3hdW3ldLCBpbml0LmJvYXJkW3R4XVt0eV0pOwogICAgICAgIGluaXQuaXggPSB4LCBpbml0Lml5ID0geTsKICAgICAgICBpZihzb2x2ZWQpICByZXR1cm4gc29sdmVkOwogICAgICAgIHN1Ym14ZGVwID0gbWluKHN1Ym14ZGVwLCB2YWwpOwogICAgfQogICAgcmV0dXJuIHN1Ym14ZGVwOwp9CmludCBtYWluKCkgewogICAgaW50IHRlc3QsIGksIGosIGssIGluaXRIOwogICAgaW50IGNhc2VzID0gMDsKICAgIGZvcihpID0gMCwgayA9IDA7IGkgPCA0OyBpKyspCiAgICAgICAgZm9yKGogPSAwOyBqIDwgNDsgaisrKQogICAgICAgICAgICBwb3NbKytrXVswXSA9IGksIHBvc1trXVsxXSA9IGo7CiAgICBmb3IoaSA9IDA7IGkgPCA0OyBpKyspCiAgICAgICAgZm9yKGogPSAwOyBqIDwgNDsgaisrKQogICAgICAgICAgICBmb3IoayA9IDE7IGsgPCAxNjsgaysrKQogICAgICAgICAgICAgICAgSHRhYmxlW2ldW2pdW2tdID0gYWJzKGkgLSBwb3Nba11bMF0pICsgYWJzKGogLSBwb3Nba11bMV0pOwogICAgc2NhbmYoIiVkIiwgJnRlc3QpOwogICAgd2hpbGUodGVzdC0tKSB7CiAgICAgICAgY2FzZXMrKzsKICAgICAgICBmb3IoaSA9IDA7IGkgPCA0OyBpKyspIHsKICAgICAgICAgICAgZm9yKGogPSAwOyBqIDwgNDsgaisrKSB7CiAgICAgICAgICAgICAgICBzY2FuZigiJWQiLCAmayk7CiAgICAgICAgICAgICAgICBpbml0LmJvYXJkW2ldW2pdID0gazsKICAgICAgICAgICAgICAgIGlmKGluaXQuYm9hcmRbaV1bal0gPT0gMCkgewogICAgICAgICAgICAgICAgICAgIGluaXQuaXggPSBpLCBpbml0Lml5ID0gajsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBpZihzb2x2YWJsZSgpKSB7CiAgICAgICAgICAgIHNvbHZlZCA9IDAsIGluaXRIID0gbXhkZXAgPSBIKCk7CiAgICAgICAgICAgIGlmKCFteGRlcCkgewogICAgICAgICAgICAgICAgcHV0cygiIik7CiAgICAgICAgICAgICAgICBjb250aW51ZTsKICAgICAgICAgICAgfQogICAgICAgICAgICB3aGlsZShzb2x2ZWQgPT0gMCkKICAgICAgICAgICAgICAgIG14ZGVwID0gSURBKDAsIGluaXRILCAtMSk7CiAgICAgICAgICAgIC8vcHJpbnRmKCIlZFxuIiwgc29sdmVkKTsKICAgICAgICB9ZWxzZSB7CiAgICAgICAgICAgIHB1dHMoIlRoaXMgcHV6emxlIGlzIG5vdCBzb2x2YWJsZS4iKTsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gMDsKfQo=