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][N]. Một con chuột đi từ ô đầu tiên góc trái (A[O][0]) đến ô cuối cùng góc phải (A[N-1][N-1]) 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.

Hãy đưa ra một 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.

Đầu vào:

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][N].

Ràng buộc: T, N, A thoa măn ràng buộc: 1 <= T <= 10; 2 <= N <= 10; O <= A[i][j] <= 1.

Đầu ra: Đư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.

Input:

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

Output:

DRDDRR 
DDRDRRDR DDRDRRRD DRDDRRDR DRDDRRRD DRRRRDDD