[DSA-QuayLui-NhanhCan].Di chuyển trong mê cung 2.

Cho một mê cung bao gồm các khối được biểu diễn như một ma trận nhị phân A[N+1][N+1]. Một con chuột đi từ ô đầu tiên góc trái (A[1][1]) đến ô cuối cùng góc phải (A[N][N]) theo nguyên tắc: Down (D): Chuột được phép xuống dưới nếu ô dưới nó có giá trị 1. Right (R): Chuột được phép sang phải dưới nếu ô bên phải nó có giá trị 1. Left (L): Chuột được phép sang trái dưới nếu ô bên trái nó có giá trị 1. Up (U): Chuột được phép lên trên nếu ô trên nó có giá trị 1. Hãy đưa ra tất cả các hành trình của con chuột trên mê cung. Đưa ra -1 nếu chuột không thể đi đến đích.

Input Format

Dòng đầu tiên đưa vào số lượng bộ test T. Những dòng kế tiếp đưa vào các bộ test. Mỗi bộ test gồm hai phần: phần thứ nhất đưa vào số N là kích cỡ của mê cung; dòng tiếp theo đưa vào ma trận nhị phân A[N+1][N+1]. T, N, A[i][j] thỏa mãn ràng buộc: 1≤T ≤10; 2≤N≤10; 0≤A[i][j]≤1

Constraints

.

Output Format

Đưa ra các xâu ký tự được sắp xếp, trong đó mỗi xâu là một đường đi của con chuột trong mê cung. In ra đáp án theo thứ tự từ điển. Đưa ra -1 nếu chuột không đi được đến đích.

Ví dụ:

Dữ liệu vào

2
4
1 0 0 0
1 1 0 1
0 1 0 0
1 1 1 1
5
1 0 0 0 0
1 1 1 1 1
1 1 0 0 1
0 1 1 1 1
0 0 0 1 1

Dữ liệu ra

DRDDRR
DDRDRRDR DDRDRRRD DDRURRRDDD DDRURRRDDLDR DRDDRRDR DRDDRRRD DRRRRDDD DRRRRDDLDR