F.R.I.E.N.D.S

4

7 votes
Segment Trees, Advanced Data Structures, Data Structures
Problem

There are People, -th person wants to be friend with all the person between .

A friendship is possible between two distinct person if and only if both of them wants to be friends with each other i.e, -th and -th person can be friend only if          and      .

Print the total number of possible friendship.

 Input format

  • The first line contains  denoting the number of test cases.
  • The first line of each test case contains integers , denoting the number of people.
  • The next lines contain and .

Output format

For each test case print the total number of possible friendship in a separate line.

Constraints



The sum of over all test cases does not exceed

Sample Input
1
6
2 4
1 3
5 6
1 2
1 2
1 6
Sample Output
3
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Friendship is only possible between , and .

Editor Image

?