The Wall is a colossal defence along the northern border of the seven kingdoms, defending the realm from the wildlings who live beyond. It is defended and held by the Sworn Brothers of the Night's Watch, and since the white walkers did not return for the past eight thousand years, the Night's Watch has mostly shifted its focus to preventing the wildlings from crossing south of the Wall. They divided it into security squarcs (a squarc is half arc half a square shape), namely into N by M squarcs, and employed two types of defences:
These two types of defences are fixed and assigned to each squarc in order to defend it.
You are given a set of points representing the coordinates of the wildlings who are climbing the wall, no point lays outside or on the borders of any squarc, what is the minimum number of defences that you have to use in order to stop the wildlings and defend the seven kingdoms.
The first line contains one integer T, the number of test cases. Each test case starts with a single line containing three integers: ( 1 ≤ N ≤ 100) , ( 1 ≤ M ≤ 100), the number of squarcs along the x and the y axes and ( 1 ≤ P ≤ 10, 000), The next P lines each of which consists of two real numbers ( 0 < x < N), ( 0 < y < M + N / 2) describing the coordinates of the wildling.
For each test case, print on a single line, a single number representing the minimum number of defences that you have to use in order to stop the wildlings.
1
4 4 9
3.1 1.9
0.4 1.4
1.4 2.6
3.2 2.2
2.2 5.6
2.7 4.3
1.2 4.0
1.2 4.5
2.8 3.6
3
Name |
---|