405162: GYM101808 B Amer and Graphs

Amer loves graph algorithms, every morning when he wakes up, he draws a random graph and applies all kinds of graph algorithms on it.

Today, he decided to make things more interesting. First, he wrote down n undirected edges in a row, numbered from 1 to n. Then, for every two integers 1 ≤ i ≤ j ≤ n, he draws a graph that consists of all edges numbered between i and j (inclusive).

Drawing the same graph many times is boring, so Amer wants to know the number of pairs of equal graphs he will draw i.e. the number of pairs of intervals that represent the same graph. Can you help Amer?

The first line contains one integer T: the number of test cases.

Each test case starts with a line that consists of one integer n, the number of edges Amer wrote down. (1 ≤ n ≤ 2000)

n lines follow, the i^th line contains two integers u and v, which means that the i^th edge connects nodes u and v. (1 ≤ u, v ≤ 2 * n)

For each test case output the number of pairs of equal graphs Amer will draw.

1
4
1 2
1 2
3 1
1 2

5

Two graphs are considered equal if they have the exact same edges.

For example :

if graph G1 has edges ({1, 2}, {3, 1}) and graph G2 has edges ({1, 2}, {1, 2}, {3, 1})

G1 and G2 are not considered equal.

if graph G3 has edges ({1, 2}, {3, 1}) and graph G4 has edges ({3, 1}, {1, 2})

G3 and G4 are considered equal.