#2335 North-Western Winds

5 s   128 MB  

Description

A strong North-Western wind is blowing. When sailing this means that you can sail to the East, to the South or to any direction between East and South. It is impossible to go either North- or Westwards.

In the ocean there are a large number of small islands. These islands are described by coordinate pairs (x, y) on a grid. The positive y-direction is Northwards and the positive x-direction is Eastwards. We’d like to sail from one island to another. For how many pairs of islands is this possible? (Note: a pair consists of two different islands.)

Input

The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:

Output

For every test case in the input file, the output should contain a single number, on a single line: the number of pairs of islands for which you can sail from one to the other.

Sample Input

Sample Output

2
4
-10 -10
-10 10
10 -10
10 10
3
1 3
2 2
3 1
5
3

Source

BAPC 2005