• محدودیت زمان: ۳ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

دیواری به شکل یک جدول $2 \times n$ داریم. می‌توانیم این دیوار را به صورت $n$ ستون در نظر بگیریم که در هر ستون دو ردیف بالا و پایین وجود دارد.

روی دیوار $k$ پریز برق وجود دارد. هر پریز، کاملاً یکی از واحدهای بالایی یا پایینی یک ستون را اشغال می‌کند.

می‌خواهیم این دیوار را کاغذ دیواری کنیم. هر تکه کاغذ دیواری، به شکل یک مستطیل است و کاغذ دیواری به هر ابعادی را به میزان کافی داریم. کاغذ دیواری‌ها نباید روی پریزها را بپوشانند و همچنین نمی‌خواهیم آن‌ها را پاره کنیم.

می‌خواهیم طوری این کار انجام شود که تعداد کاغذ دیواری‌های مصرفی کمینه شود (دقت کنید ابعاد کاغذ دیواری‌ها اهمیتی ندارد و هدف کمینه کردن تعداد آن‌هاست). از شما می‌خواهیم این تعداد کمینه را محاسبه کنید.

ورودی

در سطر اول ورودی، عدد صحیح $t$ به شما داده می‌شود که تعداد تست‌های ورودی را نشان می‌دهد. $$1 \leq t \leq 3 \times 10^5$$

سپس در سطر اول هر تست، به ترتیب، دو عدد صحیح $n$ و $k$ که با یک فاصله از هم جدا شده‌اند آمده است که نشان‌دهنده‌ی تعداد ستون‌های دیوار و تعداد پریزهای روی دیوار هستند.

$$1 \leq n \leq {10}^{18} \quad , \quad 1 \leq k \leq \min{2n, 3 \times 10^5}$$

تضمین می‌شود $\sum k$ برای همه تست‌ها حداکثر $3 \times 10^5$ باشد.

در $k$ سطر بعدی در هر سطر، کارکتر $r_i$ که برابر u یا d است و سپس با یک فاصله عدد صحیح $c_i$ آمده است. این دو عدد، موقعیت پریز $i$ام را نشان می‌دهند.

$$r_i \in {u, d} \quad \quad 1 \leq c_i \leq n$$

تضمین می‌شود هیچ دو پریزی در موقعیت یکسان قرار ندارد.

خروجی

خروجی $t$ سطر دارد، در هر سطر پاسخ تست متناظر یعنی کمترین تعداد تکه کاغذ دیواری را چاپ کنید.

مثال

ورودی نمونه ۱

4
1 1
d 1
4 2
d 3
u 3
1000000000000 0
4 2
u 1
d 4

خروجی نمونه ۱

1
2
1
2

ورودی نمونه ۲

1
2 1
u 2

خروجی نمونه ۲

2