I have bought an island where I want to plant trees in rows and columns. So, the trees will form a rectangular grid and each of them can be thought of having integer coordinates by taking a suitable grid point as the origin.

But, the problem is that the island itself is not rectangular. So, I have identified a simple polygonal area inside the island with vertices on the grid points and have decided to plant trees on the grid points lying strictly inside the polygon.

Figure: A sample of my island

For example, in the above figure, the green circles form the polygon, and the blue circles show the position of the trees.

Now, I seek your help for calculating the number of trees that can be planted on my island.

Input starts with an integer T (≤ 80), denoting the number of test cases.

Each case starts with a line containing an integer N (3 ≤ N ≤ 10000) denoting the number of vertices of the polygon. Each of the next N lines contains two integers x_i y_i (-10⁶ ≤ x_i, y_i ≤ 10⁶) denoting the co-ordinate of a vertex. The vertices will be given in clockwise or anti-clockwise order. And they will form a simple polygon.

For each case, print the case number and the total number of trees that can be planted inside the polygon.

Dataset is huge, use faster I/O methods.