The 15-puzzle is a very popular game; even if you don't know it by that name, you've seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. The objective of the puzzle is to arrange the tiles so that they are ordered as Fig 1.

Fig 1: Goal Configuration	Fig 2: A random puzzle position

Here the only legal operation is to exchange missing tile with one of the tiles with which it shares an edge. As an example, the following sequence of moves changes the status of a puzzle in Fig 2.

The missing Tile moves right. Denoted by R	The missing Tile moves left. Denoted by L	The missing Tile moves upwards. Denoted by U	The missing Tile moves down. Denoted by D

The letters in the previous row indicate which neighbor of the missing tile is swapped with it at each step; legal values are 'R','L','U' and 'D', for RIGHT, LEFT, UP, and DOWN, respectively.

Given an initial configuration of a 15-puzzle you will have to determine the steps that would make you reach the final stage. You have to find the minimum number of steps to solve the puzzle. If there are several solutions print the one that comes lexicographically earlier. If there is no solution or you need more than 35 moves; report so.

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains a blank line and 16 integers in 4 lines representing the initial board. 0 denotes blank. You may assume that every integer from 0 to 15 occurs exactly once in a board. And you may also assume that you need at least one move to solve the puzzle.

For each case of input, print the case number first. Then if there is no solution, or you need more than 35 moves, print This puzzle is not solvable.. Otherwise print the steps in a line. If several solutions are there taking minimum steps, print the one that is lexicographically smallest.