+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
پارسا می‌خواهد در آزمون مرحله یک المپیاد شرکت کند. او در آزمون‌ها به استراتژی ثابتی پایبند است: سؤال‌ها را به ترتیب از $1$ تا $n$ بررسی می‌کند، هر سؤالی که حل شود را همان‌جا علامت می‌زند و به سؤال بعدی می‌رود. او هرگز به عقب برنمی‌گردد و هیچ سؤالی را دوبار پاسخ نمی‌دهد. در یک آزمون تمرینی، پارسا برخی سؤال‌ها را نتوانسته حل کند و آن‌ها را خالی گذاشته است.
او در کل به $m$ سوال در پاسخ‌برگ پاسخ داده است. $i$-امین سوالی که به آن پاسخ داده است، سوال $p_i$ است که برای آن گزینه‌ی $c_i$ را در پاسخ‌برگ وارد کرده است.
پارسا گمان می‌کند **حداکثر یک‌بار در وارد کردن شماره سؤال‌ها روی پاسخ‌برگ اشتباه کرده است**. تعریف دقیق یک‌بار اشتباه چنین است: در یک **بازه متوالی** از پاسخ ها برای سوالات، برای هر سوال شماره سؤالی که پارسا برای آن پاسخ را ثبت کرده به اندازه عدد صحیح غیرصفر $d$ جابه‌جا شده است؛ یعنی پاسخ‌های آن بازه به‌جای سؤال‌های $\{p_\ell,\dots,p_r\}$ روی سؤال‌های $\{p_\ell+d,\dots,p_r+d\}$ ثبت شده‌اند (یا برعکس، معادل با این‌که «سؤالات مقصود» او در آن بازه $\{p_i-d\}$ بوده‌اند). خارج از این بازه، هیچ جابه‌جایی رخ نداده است. این اشتباه بیش از یک‌بار رخ نداده یا ممکن است اصلاً رخ نداده باشد.
توجه کنید که پارسا پاسخ‌ها را **به ترتیب** و بدون تکرار وارد کرده است؛ بنابراین دنباله «سؤالات پاسخ داده شده» باید صعودی و در بازهٔ $[1..n]$ باشد و هیچ سؤالی دوبار پاسخ داده نشده باشد.
شما پاسخ برگ را دارید و معلوم نیست که کجا و به چه شکلی اشتباه انجام شده. هدف شما این است که با فرض امکان وقوع «حداکثر یک‌بار اشتباه» به شکل فوق، **بیشترین نمره ای که پارسا با درست وارد کردن سوالات می‌توانست بدست بیاورد**(تعداد پاسخ‌های درست نسبت به کلید آزمون) را محاسبه کنید.
# ورودی
در خط اول ورودی عدد $T$ (تعداد تست‌ها) آمده است. سپس برای هر تست:
- خط اول شامل دو عدد صحیح $n$ و $m$ است؛ به‌ترتیب تعداد کل سؤال‌ها و تعداد سؤال‌هایی که پارسا پاسخی برای آن‌ها وارد کرده است.
- خط دوم رشته‌ای $S$ با طول $n$ شامل حروف `A` تا `E` است که کلید صحیح آزمون را نشان می‌دهد؛ $S[i]$ پاسخ صحیح سؤال $i$ام است.
- سپس $m$ خط می‌آید؛ در هر خط یک عدد صحیح $p_i$ $(1 \le p_i \le n)$ و یک حرف $c_i \in \{A,B,C,D,E\}$ آمده است. این‌ها بیان می‌کنند پارسا روی پاسخ‌برگ برای سؤال $p_i$ گزینهٔ $c_i$ را علامت زده است.
- تضمین می‌شود $p_1 < p_2 < \dots < p_m\ $.
# خروجی
برای هر تست، یک خط شامل یک عدد چاپ کنید: بیشترین تعداد پاسخ‌های درست که می‌توان برای پارسا فرض کرد.
# محدودیت‌ها
$$
1 \le T \le 10^4
$$
$$
1 \le n \le 5000,\quad 0 \le m \le n
$$
$$
\sum n \le 5000
$$
# مثال‌ها
## ورودی نمونه ۱
```
4
5 4
AECDB
1 A
2 A
4 C
5 B
7 2
AAACDAA
1 C
3 D
7 2
AAACDAA
1 C
2 D
10 5
ABECCDBAEA
3 B
4 E
6 C
8 A
10 E
````
## خروجی نمونه ۱
```
3
1
2
4
````