Maxsus Harakatlar

Input

Birinchi qator bir butun $t$ (1 \le t \le 10^5) ni o'z ichiga oladi — bitta kirish faylida test holatlari soni.

Har bir test holati ikki qator bilan tavsiflanadi. Birinchi qator $n$, $x$, $y$ butun sonlarini o'z ichiga oladi — $s$ satrining uzunligi va boshlang'ich nuqtaning koordinatalari (1 \le n \le 2 \cdot 10^5), (-10^9 \le x, y \le 10^9).

Ikkinchi qator $n$ uzunlikdagi $s$ satrini o'z ichiga oladi (s_i \in \{\mathtt{R}, \mathtt{L}, \mathtt{D}, \mathtt{U}\}).

Barcha test holatlari bo'yicha $n$ lar yig'indisi 2 \cdot 10^5 dan oshmasligi kafolatlanadi.

Output

Har bir test holati uchun maxsus nuqtalar sonini chiqaring.

Examples

Note

Birinchi test holatida jarayon quyidagicha ko'rinadi:

1. Dastlab, biz $(1,1)$ da turamiz.

2. Biz chapga harakat qilamiz, shuning uchun $(0,1)$ da turamiz.

3. Biz yuqoriga harakat qilamiz, shuning uchun $(0,2)$ da turamiz.

4. Biz pastga harakat qilamiz, shuning uchun $(0,1)$ da turamiz.

5. Biz yana yuqoriga harakat qilamiz, shuning uchun $(0,2)$ da turamiz.

6. Biz yana pastga harakat qilamiz, shuning uchun $(0,1)$ da turamiz.

Bu yerda eng ko'p tashrif buyurilgan nuqta $(0,1)$ bo'lib, u $3$ marta tashrif buyurilgan. Barcha nuqtalar orasida faqat bitta nuqta $3$ marta tashrif buyurilgan.

Ikkinchi test holatida jarayon quyidagicha ko'rinadi:

1. Dastlab, biz $(1,1)$ da turamiz.

2. Biz chapga harakat qilamiz, shuning uchun $(0,1)$ da turamiz.

3. Biz o'ngga harakat qilamiz, shuning uchun $(1,1)$ da turamiz.

4. Biz chapga harakat qilamiz, shuning uchun $(0,1)$ da turamiz.

5. Biz pastga harakat qilamiz, shuning uchun $(-1,1)$ da turamiz.

Bu yerda eng ko'p tashrif buyurilgan nuqtalar $(0,1)$ va $(1,1)$ bo'lib, ular $2$ marta tashrif buyurilgan, shuning uchun javob $2$.

Scoring

1. ($2$ ball): n \le 2;

2. ($8$ ball): s_i \in \{\mathtt{L}, \mathtt{R}\};

3. ($10$ ball): (-100 \le x, y \le 100) - Bu jarayonning har qanday nuqtasida kafolatlanadi;;

4. ($10$ ball): (1 \le \sum n \le 500) ;

5. ($20$ ball): qo'shimcha cheklovlar yo'q;