Our hardworking Ishan is a business tycoon now and has lots of offices in Silicon valley. But he is bored of sleeping in his offices. 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 offices in the city. Each of Ishan's office 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 offices is as small as possible. Find the number of possible house locations in the city to help out Ishan build a home.

More than one office can be located at the same point.

Houses and offices 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.