HK là người canh giữ một mê cung bí ẩn.

Trong cuộc thi Olympic Tin học sinh viên vòng 2, các thí sinh sẽ phải vượt qua mê cung của HK để chứng minh khả năng của mình. Nhiệm vụ của HK là thiết kế mê cung sao cho càng nhiều vị trí xuất phát khiến thí sinh bị mắc kẹt càng tốt.

Mê cung có dạng một hình chữ nhật gồm n hàng và m cột. Mỗi ô trong mê cung chứa một mũi tên chỉ một trong bốn hướng:

• ~U~ - đi lên
• ~D~ - đi xuống
• ~L~ - đi sang trái
• ~R~ - đi sang phải

Để bắt đầu thử thách, thí sinh sẽ được đưa vào mê cung thông qua một cổng dịch chuyển. Cổng này có thể đưa thí sinh đến bất kỳ ô nào trong mê cung, và thí sinh không được lựa chọn trước mình sẽ xuất hiện ở đâu.

Ngay khi xuất hiện tại một ô, thí sinh bắt buộc phải di chuyển sang ô kế tiếp theo hướng mà ô hiện tại chỉ định. Thí sinh không thể thay đổi hướng hoặc đứng yên.

Nếu hướng di chuyển đưa thí sinh ra ngoài mê cung, thí sinh đã thoát thành công.

Ngược lại, nếu thí sinh quay trở lại một ô mà mình đã từng đi qua, từ đó quá trình di chuyển sẽ lặp lại vô hạn. Khi đó, thí sinh bị mắc kẹt trong mê cung.

Tuy nhiên, HK chưa hoàn thiện mê cung. Một số ô chưa có mũi tên và được ký hiệu bằng ~?~. Trước khi cuộc thi bắt đầu, HK được phép lựa chọn hướng cho từng ô ~?~.

HK muốn tận dụng cơ hội này để tạo ra một mê cung khó nhất có thể. Cụ thể, anh ta muốn lựa chọn hướng cho các ô ~?~ sao cho số lượng vị trí mà thí sinh có thể xuất hiện và bị mắc kẹt mãi mãi là lớn nhất.

Hãy giúp HK tính số lượng vị trí xuất phát lớn nhất khiến thí sinh bị mắc kẹt bằng cách gán hướng cho các ô ~?~ một cách tối ưu.

Đầu vào

Dòng đầu tiên chứa một số nguyên ~T~ là số lượng bộ test. ~(1 \le T \le 10^4)~

Với mỗi bộ test:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ lần lượt là số hàng và số cột của mê cung. ~(1 \le n, m \le 1000)~

• ~n~ dòng tiếp theo, mỗi dòng chứa một xâu gồm ~m~ ký tự mô tả hướng di chuyển của các ô trong mê cung. Mỗi ký tự là một trong:

  • ~U~ - di chuyển lên trên.
  • ~D~ - di chuyển xuống dưới.
  • ~L~ - di chuyển sang trái.
  • ~R~ - di chuyển sang phải.
  • ~?~ - ô chưa được HK quyết định hướng di chuyển.

Đảm bảo rằng tổng số ô ~n * m~ trên tất cả các bộ test không vượt quá ~10^6~.

Đầu ra

Với mỗi bộ test, in ra một số nguyên duy nhất là số lượng lớn nhất các ô mà từ đó thí sinh có thể bắt đầu và bị mắc kẹt mãi mãi sau khi HK gán hướng cho tất cả các ô ? một cách tối ưu.

Giới hạn

~20\%~ số điểm: ~n * m \le 9~ ở mỗi bộ test, ~T \le 10~.

~25\%~ số điểm: ~n * m \le 2000~ ở mỗi bộ test, tổng ~n * m~ trên tất cả bộ test không vượt quá ~2000~.

~25\%~ số điểm: Tổng ~n * m~ trên tất cả bộ test không vượt quá ~10^5~.

~30\%~ số điểm: Không có ràng buộc gì thêm.

Ví dụ

Đầu vào

3
3 3
UUU
L?R
DDD
2 3
RRU
??D
3 3
RRD
U?D
ULL

Đầu ra

0
2
9

Giải thích

Ở bộ test thứ nhất, dù HK chọn hướng nào cho ô ~?~ thì thí sinh cũng có thể thoát khỏi mê cung.

Ở bộ test thứ hai, các ô đã được điền đều có thể thoát ra ngoài được, HK chỉ có thể điền 2 ô còn lại lần lượt là ~R~, ~L~ khiến thí sinh qua lại mãi nên kết quả là ~2~.

Ở bộ test thứ ba, ~8~ ô ngoài rìa tạo thành một chu trình khép kín nên dù ô ~?~ ở giữa HK có gán là gì thì thí sinh cũng không thể thoát khỏi mê cung nên đáp án là ~9~.