404410: GYM101502 B Linear Algebra Test

Dr. Wail is preparing for today's test in linear algebra course. The test's subject is Matrices Multiplication.

Dr. Wail has n matrices, such that the size of the i^th matrix is (a_i × b_i), where a_i is the number of rows in the i^th matrix, and b_i is the number of columns in the i^th matrix.

Dr. Wail wants to count how many pairs of indices i and j exist, such that he can multiply the i^th matrix with the j^th matrix.

Dr. Wail can multiply the i^th matrix with the j^th matrix, if the number of columns in the i^th matrix is equal to the number of rows in the j^th matrix.

The first line contains an integer T (1 ≤ T ≤ 100), where T is the number of test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 10⁵), where n is the number of matrices Dr. Wail has.

Then n lines follow, each line contains two integers a_i and b_i (1 ≤ a_i, b_i ≤ 10⁹) (a_i ≠ b_i), where a_i is the number of rows in the i^th matrix, and b_i is the number of columns in the i^th matrix.

For each test case, print a single line containing how many pairs of indices i and j exist, such that Dr. Wail can multiply the i^th matrix with the j^th matrix.

1
5
2 3
2 3
4 2
3 5
9 4

5

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

In the first test case, Dr. Wail can multiply the 1^st matrix (2 × 3) with the 4^th matrix (3 × 5), the 2^nd matrix (2 × 3) with the 4^th matrix (3 × 5), the 3^rd matrix (4 × 2) with the 1^st and second matrices (2 × 3), and the 5^th matrix (9 × 4) with the 3^rd matrix (4 × 2). So, the answer is 5.