Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Make it Manhattan
Time Limit: 2000MSMemory Limit: 65536K
Total Submissions: 1088Accepted: 467

Description

Chaos City has grown out of control. Building have been built everywhere and the city layout is a complete mess. The mayor decided that this must come to an end, and wants to create a nice, structed city.

After some research, he found the ideal way to make this happen. Inspired by the New York district of Manhanttan, he wants all buidlings organized in a rectangular grid, separated by avenuesrunning from North to South and streets running from West to East. These streets and avenues should all be separated by the same distance D.

In the current situation, the buidlings are already organized in a rectangular grid. In fact each buidling fills exactly one square in this grid. However, with all the buildings randomly scattered across the city, it may be impossible to build the roads without demolishing a couple of buildings. To keep most citizens happy, the mayor wants to demolish as few buidlings as possible. Given the current locations of the buidlings, what's this minimum number?

The above picture illustrates the problem. The shaded squares are the initial locations of the buidlings. If the roads should be separated by a distance of three, the thick lines indicate the optimal placement of the roads and one building has to be demolished.

Input

The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:
One line with two integers D and N, separated by a single space, satisfying 1 <=D <= 1000 and 0 <= N <= 100000: the distance between two roads, and the number of buidling in the city respectively.
N lines with two integers xi and yi, separated by a single space, satisfying -109 <= xi, yi <= 109: the positions of the buidlings.

Output

For every testcase in the input, the output should contains a single line with the minimum number of buidling that has to be demolished.

Sample Input

1
3 10
1 0
2 0
3 0
4 0
1 2
0 3
1 5
3 5
4 2
-2 2

Sample Output

1

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator