Sir Moo Moo Honey is the King of Honeycomb kingdom. Everyone knows him as Honey King. Honeycomb kingdom is a hexagonal grid of infi- nite size where each cell is a hexagon. Like any other grid system, the Honeycomb grid can be represented by a 2D coordinate system as the figure on the right. From each cell if we go to up (down) di- rection then the y value of a coordinate de- creases (increases) and x value remains same. Similarly if we go to up-left (down-right) direc- tion the x value of a coordinate decreases (in- creases) and y value remains same. But for the direction up-right (down-left) the x value in- creases (decreases) as well as y value decreases (increases). So for a cell (x, y), there are six sur- rounding cells, up(x, y − 1), down(x, y + 1), up−left(x−1, y), down−right(x+1, y), up−right(x+1, y−1) and down−left(x− 1, y + 1). Honey King does not love his people much. He always wanted to separate them from his beautiful palace. He came up with a new idea to do this. He will build a wall outside of his palace to separate the people of Honeycomb from his palace. The wall will be a hexagonal shaped ring of hexagonal cells. As the king is a disciplined person he likes regularity and the wall should be a regular hexagon (all six sides of the hexagon should be equal). There are some beautiful cells in in the honeycomb grid. King’s palace is in one of the beautiful cells. Honey King wants to build the wall in such way that all the beautiful cells remain inside the wall. Also the king wants to minimize the area inside the wall. For example, if cell (0, 0), (−1, 0) and (−2, 2) are beautiful cells, then one way to build the wall is as follows: The shaded cells form the wall in the image above. Help Honey King to build the smallest regular hexagonal wall in Honeycomb kingdom such that all the beautiful cells remain inside the wall. Input First line of the input contains an integer number T (T ≤ 200), denoting the number of test cases. First line of each test case contains an integer number N (1 ≤ N ≤ 100000), number of beautiful cells. Next N lines will contain N pairs of space separated integers Xi and Yi (−104 ≤ Xi,Yi ≤ 104, 1 ≤ i ≤ N), where (Xi,Yi) is the coordinate of the i-th beautiful cell. No two coordinates in a single test will be same. Note that, sum of N in all test cases will be less than 200000.
2/2 Output For each test case, print the test case number and number of hexagonal cells inside the smallest regular hexagonal wall containing all beautiful cells. Note: For second test case, see the example in the problem description. Sample Input 2 1 00 3 00 -1 10 -2 22 Sample Output Case 1: 1 Case 2: 7