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ự $RLUD$ và "$\mathrm{\_}$" , bạn hãy đếm số cách điền một trong bốn kí tự $RLUD$ vào hết các kí tự "$\mathrm{\_}$" để 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ự $RLUD$ và "$\mathrm{\_}$", 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=(\genfrac{}{}{0ex}{}{10}{5})$.