VegiCat-та $n$ тұйық бүтін санды кесінді $[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]$ бар.

Ол әрбір $[l_i, r_i]$ кесіндісінен бір бүтін $a_i$ санын таңдау арқылы $a_1, a_2, \ldots, a_n$ тізбегін құрастырғысы келеді. Яғни, әрбір $1 \le i \le n$ үшін $l_i \le a_i \le r_i$ орындалады.

Егер әрбір $1 \le j < i$ үшін $a_i > a_j$ болса, онда $i$ орыны рекордтық орын деп аталады. Атап айтқанда, $1$-ші орын әрқашан рекордтық орын болады.

VegiCat-қа рекордтық орындар санын барынша азайтуға көмектесіңіз. Осы ең аз санды шығарыңыз.

Кіріс деректері

Бірінші жолда бір бүтін сан $T$ ($1 \le T \le 10^4$) — тест жағдайларының саны берілген. Одан кейін тест жағдайларының сипаттамасы беріледі.

Әр тест жағдайының бірінші жолында бір бүтін сан $n$ ($1 \le n \le 10^6$) — кесінділер саны берілген.

Келесі $n$ жолдың $i$-шісінде $i$ орынында қолжетімді кесіндіні сипаттайтын екі бүтін сан $l_i, r_i$ ($-10^9 \le l_i \le r_i \le 10^9$) берілген.

Барлық тест жағдайлары бойынша $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$-ші орын рекорд емес, өйткені оның мәні осыған дейін кездескен максимумға тең.