CRAN03 - Howard The Saviour

Howard is now an astronaut. After a successful journey to the space station, he is now headed towards Mars this time for yet another interesting task. But this task of his will save the humanity. Some alien pirates have placed bombs on a very large rectangular grid. Some of the bombs are Master bombs. Master bombs have at least one bomb on their left hand side, right hand side, above and below their position.

As soon as Howard reaches Mars he notes down the coordinates of the bombs that have been planted. Now he has to count the Master bombs that have been placed on Mars.

Given position of all the bombs help Howard to count the number of Master Bombs.

Input

First line contains t, the number of test cases.

The next line contains n, the number of bombs in the grid.

Next n lines contain the coordinates of the bombs (xi, yi).

Output

Output the number of Master bombs.

Constraints

1<=t<=10

1<=n<=500

0<= xi, yi<=200

Example

Input:
2
5
1 1
0 1
1 0
6 1
1 9
8
1 1
4 2
3 1
1 2
0 2
0 1
1 0
1 3

Output: 1
2

Added by:CSI
Date:2013-02-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2018-06-21 08:57:58
NlogN is relatively easy to conceive but kinda tedious to get right. Took me 45 mins to debug the damn thing.. Shame about the constraints, with the ones Ehor proposed it would make a good classical still solvable in slower languages.
2013-02-24 02:26:02 Kevin Sebastian
this is really annoying...if a problem should be in tutorial it should be put there already not stay as classical problem for a long time
2013-02-23 22:06:12 :D
Yes the problem is trivial. As Ehor said, this can be in classical, but only a version with much bigger constraints. O(N^2) and O(maxX * maxY) should definitively fail. O(N * logN) should be the required complexity.
2013-02-19 19:24:04 STARK
i am getting correct answer for the sample test cases....are there any tricky part which i am missing in this ques ?? or please check my solution...and guide me with some hint of my mistake
2013-02-18 11:58:29 Ehor Nechiporenko
With such consraints this problem looks tutorial.
It's much more interesting to resolve this problem, when n = 10^6 and xi,yi <= 10^9.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.