#include <iostream>#include <iomanip>#include <sstream>#include <cstdio>#include <string>#include <vector>#include <algorithm>#include <complex>#include <cstring>#include <cstdlib>#include <cmath>#include <cassert>#include <climits>#include <queue>#include <map>#include <valarray>#include <bitset>#include <stack>using namespace std;#define REP(i,n) for(int i=0;i<(int)n;++i)#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)#define ALL(c) (c).begin(), (c).end()#define chmax(a,b) (a<(b)?(a=b,1):0)#define chmin(a,b) (a>(b)?(a=b,1):0)#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)typedef long long ll;typedef pair<int,int> pii;const int INF = 1<<29;const double PI = acos(-1);const double EPS = 1e-8;int mat[2][6][6];void input(int d) { for (int i=0; i<6; ++i) for (int j=0; j<6; ++j) cin>>mat[d&1][i][j];}struct state { int x1,y1,x2,y2;};bool s(int d,int i,int j) { return ((mat[d][i][j]>>5)&1) == 1;}bool t(int d,int i,int j) { return ((mat[d][i][j]>>6)&1) == 1;}string dist[6][6][6][6];inline void set(const state &s, const string &str) { dist[s.x1][s.y1][s.x2][s.y2] = str;}inline string get(const state &s) { return dist[s.x1][s.y1][s.x2][s.y2];}inline bool hole(const state &s) { if (((mat[0][s.y1][s.x1]>>4)&1) == 0 || (((mat[1][s.y2][s.x2]>>4)&1) == 0)) return true; return false;}inline bool goal(const state &s) { if (t(0,s.y1,s.x1) && t(1,s.y2,s.x2)) return true; return false;}int wk[4] = {1,0,2,3};bool wall(int d,int x,int y,int k) { return (mat[d][y][x]>>wk[k])&1;}string d[4] = {"D", "L" , "R", "U"};int dx[4] = {0, -1, 1, 0};int dy[4] = {1, 0, 0, -1};state move(int k, const state &s) { int nx1 = s.x1 + ((!wall(0,s.x1,s.y1,k))?dx[k]:0); int ny1 = s.y1 + ((!wall(0,s.x1,s.y1,k))?dy[k]:0); int nx2 = s.x2 + ((!wall(1,s.x2,s.y2,k))?dx[k]:0); int ny2 = s.y2 + ((!wall(1,s.x2,s.y2,k))?dy[k]:0); if (nx1 < 0 || nx1 >= 6 || ny1 < 0 || ny1 >= 6) nx1 = -1; if (nx2 < 0 || nx2 >= 6 || ny2 < 0 || ny2 >= 6) nx1 = -1; return (state){nx1,ny1,nx2,ny2};}string solve() { queue<state> q; state start; for (int i=0; i<6; ++i) for(int j=0; j<6; ++j) for (int k=0; k<6; ++k) for (int l=0; l<6; ++l) dist[i][j][k][l] = ""; for (int i=0; i<6; ++i) { for (int j=0; j<6; ++j) { if (s(0,i,j)) { start.x1 = j, start.y1 = i; } if (s(1,i,j)) { start.x2 = j, start.y2 = i; } } } q.push(start); set(start, "A"); while(!q.empty()) { state s = q.front(); q.pop(); const string &g = get(s); if (goal(s)) return g.substr(1); for (int k=0; k<4; ++k) { state t = move(k, s); if (t.x1 == -1) continue; if (goal(t)) return g.substr(1) + d[k]; if (hole(t)) continue; const string ng = g + d[k]; if (get(t) == "") { q.push(t); set(t, ng); } } } return "-1";}int main() { int T; cin>>T; input(0); for (int i=1; i<T; ++i) { input(i); cout<<solve()<<endl; }}
