ל-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$ אינו שיא מכיוון שערכו שווה למקסימום שנראה עד כה.