맨해튼으로 만들기

카오스 시티는 통제 불능으로 커졌다. 건물이 사방에 들어섰고 도시 배치는 완전히 엉망이다. 시장은 이제 그만두어야 한다고 결심했고, 잘 정돈된 도시를 만들고 싶어 한다.

조사 끝에 시장은 이를 실현할 이상적인 방법을 찾았다. 뉴욕의 맨해튼 지구에서 영감을 얻어, 모든 건물을 남북으로 뻗은 애비뉴와 동서로 뻗은 스트리트로 나뉜 직사각형 격자에 배치하려 한다. 이 스트리트와 애비뉴는 모두 같은 간격 D로 떨어져 있어야 한다.

현재 상태에서 건물들은 이미 직사각형 격자에 배치되어 있다. 실제로 각 건물은 이 격자의 정사각형 하나를 정확히 채운다. 그러나 건물들이 도시 전체에 무작위로 흩어져 있어서, 몇 채를 철거하지 않고서는 도로를 놓을 수 없을 수도 있다. 대부분의 시민을 만족시키기 위해 시장은 최소한의 건물만 철거하려 한다. 건물의 현재 위치가 주어졌을 때, 철거해야 하는 최소 건물 수는 얼마인가?

위 그림은 문제를 나타낸다. 음영 처리된 정사각형은 건물의 처음 위치이다. 도로가 거리 3만큼 떨어져야 한다면, 굵은 선은 도로를 놓는 최적의 위치를 나타내며 건물 하나를 철거해야 한다.

입력의 첫 줄에는 테스트 케이스의 수가 하나 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

• 두 정수 D와 N이 하나의 공백으로 구분되어 있는 한 줄. 1 ≤ D ≤ 1000, 0 ≤ N ≤ 100000. 각각 두 도로 사이의 거리와 도시에 있는 건물의 수이다.
• 두 정수 xi와 yi가 하나의 공백으로 구분되어 있는 N개의 줄. -109 ≤ xi, yi ≤ 109. 건물의 위치이다.

입력의 각 테스트 케이스에 대해, 철거해야 하는 최소 건물 수를 한 줄에 출력한다.