Our hardworking chef is bored of sleeping in his restaurants. He has decided to settle down. The first thing he must do is to find a suitable location to build a palatial home.

Think of the city as a two-dimensional grid. There are N restaurants in the city. Each of the chef's restaurant is a point denoted by (X , Y). A house can be located at a grid point (R, S) if the sum of the distances between this point and each of the restaurants is as small as possible. Find the number of possible house locations in the city to help out chef build a home.

More than one restaurant can be located at the same point.
Houses and restaurants can be located at the same point.
Every house must have integer co-ordinates. In other words, R and S are integers.
The distance between two points (A,B) and (C,D) is |A-C| + |B-D|. Here |X| is the absolute function.
Input

First line in the input contains T, number of test cases.
First line of each test case contains N, number of restaurants.
Each of the next N lines contain two integers X and Y separated by a space.

T <= 100
N <= 10^3
-10^8 <= X <=10^8
-10^8 <= Y <=10^8
Output

The number of possible locations (grid points) where houses can be built.
Example

Input:
3
5
0 0
-1 0
1 0
0 1
0 -1
5
31 11
30 -41
20 14
25 18
25 38
2
0 0
1 1

Output:
1
1
4

3
Contributors
2
Replies
3
Views
6 Years
Discussion Span
Last Post by DeanMSands3

We are not here to answer homework, If you have code or any attempt....please post.

We can't just do your homework for you, or you would never learn anything.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.