Trên lưới ô vuông vô hạn, mỗi một ô được xác định bởi hai số nguyên \(x\) và \(y\): hàng và cột của ô đó so với ô gốc.

Một Walker có thể di chuyển tới ô bên cạnh với ô nó đang đứng. Cụ thể tại vị trí \((x, y)\), một Walker có thể di chuyển như sau:

• Rẽ phải (kí hiệu \(R\)): đi sang ô \((x + 1, y)\).
• Rẽ trái (kí hiệu \(L\)): đi sang ô \((x - 1, y)\).
• Đi lên (kí hiệu \(U\)): đi sang ô \((x, y + 1)\).
• Đi xuống (kí hiệu \(D\)): đi sang ô \((x, y - 1)\).

Ban đầu Walker đang đứng ở vị trí \((0, 0)\). Cho trước vị trí ô đích của Walker và một chuỗi chỉ gồm toàn kí tự \(R\:L\:U\:D\) và "\(\_\)" , bạn hãy đếm số cách điền một trong bốn kí tự \(R\:L\:U\:D\) vào hết các kí tự "\(\_\)" để Walker khi đi theo các kí tự trên xâu có thể tới đích mà không đi vào ô nào quá \(1\) lần.

Đầu vào

Dòng đầu tiên chứa số tự nhiên \(t\) \((1 \le t \le 100)\), số lượng test con.

Mỗi test con được mô tả như sau:

• Dòng đầu tiên chứa hai số nguyên \(x\), \(y\), tọa độ ô đích mà Walker cần đến.
• Dòng thứ hai chứa một xâu chỉ gồm toàn kí tự \(R\:L\:U\:D\) và "\(\_\)", dộ dài không quá \(20\).

Đầu ra

Mỗi test con xuất ra một số tự nhiên duy nhất trên một dòng.

Ghi chú: Các testcase được sinh ngẫu nhiên và số vị trí trống không quá \(16\).

Ví dụ

Đầu vào:

2
1 3
RU_L__
5 5
__________

Đầu ra:

1
252

Giải thích:

• Trong test con đầu tiên, walker chỉ có duy nhất một cách duy chuyển là \(RUULUR\).
• Trong test con thứ hai, \(252 = \binom{10}{5}\).