لدى VegiCat عدد $n$ من المجالات الصحيحة المغلقة $[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]$.

يريد بناء متتالية $a_1, a_2, \ldots, a_n$ عن طريق اختيار عدد صحيح $a_i$ من كل مجال $[l_i, r_i]$. أي أن $l_i \le a_i \le r_i$ لكل $1 \le i \le n$.

يُسمى الموضع $i$ موضعاً قياسياً إذا كان $a_i > a_j$ لكل $1 \le j < i$. وبشكل خاص، الموضع $1$ هو دائماً موضع قياسي.

ساعد VegiCat على تقليل عدد المواضع القياسية إلى الحد الأدنى. اطبع هذا العدد الأدنى.

الإدخال

يحتوي السطر الأول على عدد صحيح $T$ ($1 \le T \le 10^4$)، وهو عدد حالات الاختبار. يلي ذلك وصف حالات الاختبار.

يحتوي السطر الأول من كل حالة اختبار على عدد صحيح $n$ ($1 \le n \le 10^6$)، وهو عدد المجالات.

يحتوي السطر $i$ من الأسطر الـ $n$ التالية على عددين صحيحين $l_i, r_i$ ($-10^9 \le l_i \le r_i \le 10^9$)، يصفان المجال المتاح عند الموضع $i$.

من المضمون أن مجموع $n$ عبر جميع حالات الاختبار لا يتجاوز $10^6$.

الإخراج

لكل حالة اختبار، اطبع عدداً صحيحاً — أقل عدد ممكن من المواضع القياسية.

أمثلة

الإدخال 1

2
4
1 1
1 100
20 20
30 30
8
-3 -1
-5 4
0 1
2 2
1 8
5 6
10 12
12 12

الإخراج 1

2
4

ملاحظة

في حالة الاختبار الأولى، إحدى المتتاليات المثلى هي $a = [1, 100, 20, 30]$. مواضعها القياسية هي $1$ و $2$.

في حالة الاختبار الثانية، إحدى المتتاليات المثلى هي $a = [-1, 4, 1, 2, 8, 6, 12, 12]$. مواضعها القياسية هي $1, 2, 5$ و $7$. الموضع $8$ ليس قياسياً لأن قيمته تساوي أكبر قيمة شوهدت حتى الآن.