Дан ориентированный граф из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$. Граф задаётся следующим образом: для каждой вершины $$$i$$$ от $$$2$$$ до $$$n$$$ заданы два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \lt i$$$). Для каждого целого числа $$$j \in [l_i, r_i]$$$ в графе есть ориентированное ребро из $$$j$$$ в $$$i$$$. Других рёбер в графе нет.
Рассмотрим второй ориентированный граф на тех же $$$n$$$ вершинах. Для любых двух различных вершин $$$x$$$ и $$$y$$$ путь из $$$x$$$ в $$$y$$$ должен существовать во втором графе тогда и только тогда, когда он существует в первом графе.
Найдите минимально возможное количество рёбер во втором графе.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — количество вершин.
Следующие $$$n-1$$$ строк описывают рёбра графа. В $$$i$$$-й из этих строк даны два целых числа $$$l_{i+1}$$$ и $$$r_{i+1}$$$ ($$$1 \le l_{i+1} \le r_{i+1} \le i$$$).
Дополнительные ограничения на входные данные:
Для каждого набора входных данных выведите одно целое число — минимально возможное количество рёбер во втором графе.
551 11 22 32 461 11 12 32 34 551 11 21 31 461 11 11 12 42 461 11 21 12 43 5
48496
В первом наборе входных данных во второй граф достаточно добавить рёбра $$$1 \to 2$$$, $$$2 \to 3$$$, $$$3 \to 4$$$ и $$$4 \to 5$$$.
Во втором наборе входных данных во второй граф достаточно добавить рёбра $$$1 \to 2$$$, $$$1 \to 3$$$, $$$2 \to 4$$$, $$$3 \to 4$$$, $$$2 \to 5$$$, $$$3 \to 5$$$, $$$4 \to 6$$$ и $$$5 \to 6$$$.
