Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3251
Copy Triangle

Time Limit: 1 Second      Memory Limit: 32768 KB

Usually, to distinguish different bacteria with naked eyes is impossible. You must reproduce them to a large enough magnification by the microscope. But in fact some bacteria can be distinguished by their bacteria colonies. A bacterial colony is a visible bunch of microorganisms that sprang from a single mother cell, and different bacteria colonies have their unique traits.

CM is an amateur biologist. In his lab, there are many kinds of bacteria, and he likes to do some research on them. Last week he found a strange bacterium called "copy triangle". Its colony grows like this:

  1. CM puts some copy triangle in the (0, 0) grid, (the left top corner).
  2. These bacteria sprang and grow in right and down grids, keeping the pattern same with the origin.
  3. Repeat step 2, (we assume the size of the container is infinite).

The following pictures show how they grow.

CM wants to research the competence of this kind of bacteria, so after they fill up with the container, (it's infinite), he puts another kind of bacteria called "crazy grow" in some grids. If the grid is not occupied by "copy triangle" these bacteria will spread to neighbor grids (up, down, left and right) which are empty, or they will be eliminated by copy triangle immediately. Now he wants to know how many grids will be occupied by "crazy grow".

Input

There are multiple test cases. The first line of input contains an integer T (T <=20), indicating the number of test cases. Then T test cases follow.

The first line of each test case contains an integer M, (0<M<=5000). CM puts "crazy grow" in M grids. Then M lines follow. Each line contains two integers Xi and Yi, which means that CM puts "crazy grow" in grids (Xi, Yi), (0<=Xi, Yi<=231-1).

Output

For each test case, output how many grids are occupied by "crazy grow".

Sample Input

2
3
1 1
2 2
4 4

3
1 1
1 3
2 2

Sample Output

35
7

Author: HUANG, Minzhi
Source: ZOJ Monthly, September 2009
Submit    Status