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

---

استاد که اخیرا زمان زیادی را تنهایی سپری می‌کند تصمیم گرفته تنهایی مار و پله بازی کند.

بازی از \(n\) خانه با شماره‌های \(1\) تا \(n\) تشکیل شده. همچنین در صفحه‌ی بازی \(l\) پله و \(s\) مار قرار دارند. پله‌ی \(i\)ام بین خانه‌های \(a_{i}\) و \(b_{i}\) \((a_{i} < b_{i})\) قرار دارد و اگر استاد در لحظه‌ای از بازی در خانه‌ی \(a_{i}\) قرار بگیرد باید با استفاده از پله به خانه‌ی \(b_{i}\) برود. مار \(i\)ام نیز بین خانه‌های \(c_{i}\) و \(d_{i}\) \((c_{i} > d_{i})\) قرار دارد و اگر استاد در لحظه‌ای از بازی در خانه‌ی \(c_{i}\) قرار بگیرد توسط مار نیش زده می‌شود و به خانه‌ی \(d_{i}\) می‌رود.

او در هر لحظه از بازی می‌تواند یک عدد مثل \(k\) بین \(1\) تا \(6\) انتخاب کند و \(k\) خانه از خانه‌ی فعلیَش جلوتر برود (به شرطی که مقصد حدکثر \(n\) باشد). بازی از خانه ۱ شروع شده و در خانه \(n\) خاتمه می‌یابد.

از آن‌جایی که تنهایی بازی کردن چندان مفرح نیست،‌ استاد تصمیم گرفته به جای بازی کردن کمینه‌ی تعداد مراحلی که نیاز دارد تا از خانه‌ی ۱ به خانه‌ی \(n\) برسد را محاسبه کند. به او در این کار کمک کنید.

توجه کنید شرکت ساخت مار و پله بازی رو طوری طراحی کرده که حداقل یک راه برای رسیدن به خانه آخر وجود داشته باشد و همچنین برسی دقیق محدودیت‌های داده شده در بخش ورودی حائز اهمیت است.

ورودی

ورودی شامل \(t\) سناریو است. اطلاعات سناریوها در خطوط متمایز و متوالی به شرح زیر برای هر سناریو می‌آید. خط اول سناریو شماره \(u\) شامل سه عدد \(n_u\)، \(l_u\) و \(s_u\) می‌شود که به ترتیب تعداد خانه‌های بازی،‌ پله‌ها و مارها را نشان می‌دهند.

خط \(i\)ام خط از \(l_u\) خط بعدی شامل دو عدد \(a_{i}\) و \(b_{i}\) می‌شود که به ترتیب نشان دهنده‌ی خانه‌های ابتدایی و انتهایی \(i\)امین پله‌اند.

نهایتا \(i\)امین خط از \(s_u\) خط بعدی شامل دو عدد \(c_{i}\) و \(d_{i}\) می‌شود که به ترتیب نشان دهنده‌ی خانه‌های سر و دم \(i\)امین ماراند. \[1 \le t \le 10\,000\] \[2 \le n_u \le 200\, 000\] \[\sum_{u=1}^t n_u \le 200 \, 000\] \[ 0 \le l_u + s_u \le n_u-2\] \[2 \le a_i < b_i \le n_u\] \[1 \le d_i < c_i < n_u\] \[a_i \ne a_j, a_i \ne c_j, c_i \ne c_j \quad (i \ne j)\]

خروجی

برای هر سناریو در خروجی کمینه‌ی تعداد مراحلی که استاد نیاز دارد تا از خانه‌ی \(1\) به خانه‌ی \(n\) برسد را در خطی جداگانه چاپ کنید.

مثال

ورودی نمونه ۱

4
100 0 0
100 2 2
7 70
8 80
82 54
99 1
30 2 0
8 23
7 18
100 1 1
5 99
99 4

خروجی نمونه ۱

17
6
3
17

توضیحات نمونه:

در سناریوی اول یکی از بهترین روش‌هایی که استاد می‌تواند پیش بگیرد این است که در هر مرحله بیشترین میزانی که می‌تواند به جلو برود. با این روش استاد پس از \(17\) مرحله به خانه‌ی \(100\) می‌رسد.

در سناریوی دوم یکی از بهترین روش‌های استاد این است که:

• در مرحله‌ی اول \(1\) خانه به جلو برود تا به خانه‌ی \(2\) برسد.
• در مرحله‌ی دوم \(6\) خانه به جلو برود تا به خانه‌ی \(8\) برسد و بعد توسط نردبان به خانه‌ی \(80\) برود.
• نهایتا پس از مراحل بالا در هر مرحله بیشترین میزانی که می‌تواند به جلو برود.

در سناریوی آخر نیز یکی از بهترین روش‌ها این است که در هر مرحله بیشترین میزانی که می‌تواند به جلو برود. دقت کنید که در این سناریو اگر استاد در خانه‌ی \(5\) قرار بگیرد باید با استفاده از پله به خانه‌ی \(99\) برود. سپس در آن خانه توسط مار نیش زده می‌شود و به خانه‌ی \(4\) برمی‌گردد.