Robot tuyết

Bạn có một robot di chuyển trên lưới vô hạn. Robot bắt đầu ở ô $(0,0)$ và thực hiện một dãy lệnh là xâu $s$ gồm các ký tự L, R, U, D.

• L: di chuyển từ $(x,y)$ sang $(x-1,y)$.
• R: di chuyển từ $(x,y)$ sang $(x+1,y)$.
• U: di chuyển từ $(x,y)$ sang $(x,y+1)$.
• D: di chuyển từ $(x,y)$ sang $(x,y-1)$.

Một dãy lệnh được gọi là hợp lệ nếu:

1. Robot xuất phát từ $(0,0)$ và kết thúc tại $(0,0)$.
2. Robot không bao giờ đi vào cùng một ô khác $(0,0)$ quá một lần.
3. Ô $(0,0)$ được thăm tối đa hai lần (lúc bắt đầu và lúc kết thúc); nếu dãy lệnh rỗng thì $(0,0)$ chỉ được thăm một lần.

Vì xâu $s$ ban đầu có thể không hợp lệ, bạn được phép:

• Xoá đi một số (có thể là tất cả hoặc không) lệnh trong $s$,
• Sau đó sắp xếp lại các lệnh còn lại theo thứ tự tuỳ ý.

Nhiệm vụ: tìm cách xoá ít lệnh nhất có thể (tức là giữ lại nhiều lệnh nhất có thể) sao cho sau khi sắp xếp lại, dãy thu được là hợp lệ. In ra dãy lệnh có độ dài lớn nhất tìm được. Nếu có nhiều đáp án, in ra bất kỳ.

Bạn phải trả lời $q$ truy vấn độc lập.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $q$ — số truy vấn.
• $q$ dòng tiếp theo, mỗi dòng chứa một xâu $s$ gồm các ký tự L, R, U, D.

Dữ liệu ra

Với mỗi truy vấn, in ra trên hai dòng:

• Dòng 1: số nguyên $k$ — số lệnh được giữ lại lớn nhất.
• Dòng 2: xâu $t$ độ dài $k$ — dãy lệnh hợp lệ thu được. Nếu $k=0$, bạn có thể in ra dòng trống hoặc bỏ qua dòng thứ hai.

Nếu có nhiều đáp án thoả mãn, in ra một đáp án bất kỳ.

Ràng buộc

• $1\le q\le 2·{10}^4$.
• $1\le |s|\le {10}^5$.
• Tổng độ dài tất cả các xâu $s$ không vượt quá ${10}^5$.

Ví dụ