1. 

/**
* Angewandte Mathematik, SS11
* Problem: 10181 15-Puzzle Problem
* http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1122
*
* @author Christoph Waldleitner
*
* Method : IDA*, Manhattan Distanz + Linear Conflict, Permutationskriteritum
* Status : Accepted
* Runtime: 2.704
*/

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main
{

public static void main(String[] args) throws Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int times = Integer.parseInt(br.readLine());
StringTokenizer st;
boolean resultIsFound;
Stack<State> openStates;

State state;

for (int x = 0; x < times; x++)
{
resultIsFound = false;
openStates = new Stack<State>();
int[] board = new int[16];
int nullstelle = -1;
for (int i = 0; i < 4; i++)
{

st = new StringTokenizer(br.readLine());
for (int j = 0; j < 4; j++)
{
int tmp;
if ((tmp = Integer.parseInt(st.nextToken())) == 0)
{
nullstelle = j + i * 4;
}
board[j + i * 4] = tmp;
}
}
state = new State(board, 0, "", nullstelle, "");
openStates.push(state);

if (state.requiredmoves > 50 || !validpermutation(board))
{
resultIsFound = true;
}

if (!resultIsFound && solve(openStates, state))
{
System.out.println(openStates.peek().solve);
} else
System.out.println("This puzzle is not solvable.");

}

}

public static boolean validpermutation(int[] board)
{
int inversations = 0;
for (int i = 0; i < 16; i++)
{
int a = board[i];
if (a != 0)
{
for (int j = i + 1; j < 16; j++)
{
int b = board[j];
if (b != 0 && b < a)
{
inversations++;
}
if (a == b)
return false;
}
} else
{
inversations += (1 + i / 4);
}
}
return (inversations % 2 == 0) ? true : false;
}

public static boolean solve(Stack<State> openStates,
State start)
{
int border = openStates.peek().getBorder();

while (true)
{
if (openStates.size() != 0)
{
// Collections.sort(openStates);
if (border > 50)
return false;

if (openStates.peek().requiredmoves == 0)
return true;
else
{
Iterator iterator = new Iterator(openStates.peek(),
openStates.peek().nullstelle,
openStates.pop().lastMove);

while (iterator.hasNext())
{
State tmp = iterator.getNext();

if (tmp.getBorder() <= border)
{
openStates.push(tmp);
}
}
}
if (openStates.size() == 0)
{
openStates.removeAllElements();
border = border + 2;
openStates.push(start);
}
}
}
}
}

class State implements Comparable<State>
{
int[] board;
int moves, requiredmoves, nullstelle;
String solve, lastMove;
Iterator iterator;

public State(int[] board, int moves, String solve, int nullstelle,
String lastMove)
{
this.board = board;
this.moves = moves;
this.solve = solve;
this.nullstelle = nullstelle;
this.lastMove = lastMove;
requiredmoves = this.requiredMoves();
}

public boolean isEqual(State other)
{
for (int i = 0; i < 16; i++)
{
if (board[i] != other.board[i])
return false;
}
return true;
}

public int getBorder()
{
return requiredmoves + moves;
}

public int requiredMoves()
{
int result = 0;
for (int i = 0; i < 16; i++)
{
int num = board[i];
if (num != 0)
{
result += Math.abs(i % 4 - (num - 1) % 4);
result += Math.abs(i / 4 - (num - 1) / 4);
}
}

for (int i = 0; i < 4; i++)
{
int isThere = 0;
int row = i * 4;
int rowEnd = row + 4;
for (int k = row; k < rowEnd; k++)
{
for (int j = row + 1; j < rowEnd + 1; j++)
{
if (board[k] == j)
{
if (board[k] < isThere)
{
result = result + 2;
isThere = 0;
} else
isThere = board[k];
break;
}
}
}
isThere = 0;
int column = i;
int columnEnd = i + 12;
for (int k = column; k <= columnEnd; k = k + 4)
{
for (int j = column + 1; j <= columnEnd + 1; j = j + 4)
{
if (board[k] == j)
{
if (board[k] < isThere)
{
result = result + 2;
isThere = 0;
} else
isThere = board[k];
break;
}
}
}

}
return result;
}

public State move(String dest)
{
int[] tmp = new int[16];
int newNullstelle = -1;
for (int i = 0; i < 16; i++)
{
tmp[i] = board[i];
}
if (dest == "R")
{
tmp[nullstelle] = tmp[nullstelle + 1];
tmp[nullstelle + 1] = 0;
newNullstelle = nullstelle + 1;
} else if (dest == "L")
{
tmp[nullstelle] = tmp[nullstelle - 1];
tmp[nullstelle - 1] = 0;
newNullstelle = nullstelle - 1;
} else if (dest == "U")
{
tmp[nullstelle] = tmp[nullstelle - 4];
tmp[nullstelle - 4] = 0;
newNullstelle = nullstelle - 4;
} else if (dest == "D")
{
tmp[nullstelle] = tmp[nullstelle + 4];
tmp[nullstelle + 4] = 0;
newNullstelle = nullstelle + 4;
}
return new State(tmp, moves + 1, solve + dest, newNullstelle, dest);
}

@Override
public int compareTo(State arg0)
{
int source = moves + requiredmoves;
int target = arg0.moves + arg0.requiredmoves;
if (source == target)
{
if (moves == arg0.moves)
return 0;
else if (moves < arg0.moves)
return 1;
else
return -1;
} else
return (source < target) ? -1 : 1;
}
}

class Iterator
{
State state, nextState;
int nullstelle;
int counter = 0;
String lastMove;

public Iterator(State state, int nullstelle, String lastMove)
{
this.state = state;
this.nullstelle = nullstelle;
this.lastMove = lastMove;
this.hasNext();
}

public State getNext()
{
State tmp = nextState;
nextState = null;
return tmp;
}

public boolean hasNext()
{
for (; counter < 4 && nextState == null; counter++)
{
switch (counter)
{
case 0:
{
if (lastMove != "R" && ((nullstelle % 4) - 1 >= 0))
{
nextState = state.move("L");
}
break;
}
case 1:
{
if (lastMove != "L" && ((nullstelle % 4) + 1 <= 3))
{
nextState = state.move("R");
}
break;
}
case 2:
{
if (lastMove != "D" && ((nullstelle / 4) - 1 >= 0))
{
nextState = state.move("U");
}
break;
}
case 3:
{
if (lastMove != "U" && ((nullstelle / 4) + 1 <= 3))
{
nextState = state.move("D");
}
break;
}
}
}
return (nextState != null);
}
}