#2335 North-Western Winds

5 s   128 MB  


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.)


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:


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

-10 -10
-10 10
10 -10
10 10
1 3
2 2
3 1


BAPC 2005