레이저 함정

BaoBao는 요즘 유명한 게임 Elden Ring을 하고 있다. 이 게임은 캐릭터를 조종해 여러 장소를 이동하는 오픈 월드 게임이다. 하지만 캐릭터가 함정에 빠질 수도 있고, 그러면 탈출 방법을 찾아야 한다. 지금 BaoBao의 캐릭터는 치명적인 레이저가 있는 2차원 평면에 갇혀 있다. 레이저 발생기가 $n$개 있으며, 각 발생기는 점으로 볼 수 있다. 발생기끼리는 모든 쌍마다 레이저 빔을 쏘므로 빔은 모두 $\frac{n(n-1)}{2}$개이다. 각 빔은 발생기 점에서 시작해 발생기 점에서 끝나며, 무한히 뻗지 않는다.

BaoBao는 $(0, 0)$에서 출발해 어떤 레이저 빔이나 발생기에도 닿지 않고 $(10^{10^{10^{10^{10}}}}, 10^{10^{10^{10^{10}}}})$까지 탈출하려고 한다. 이를 위해 BaoBao는 친구 DreamGrid에게 발생기를 몇 개든 제거해 달라고 요청할 수 있다. 발생기를 제거하면 그 발생기를 시작점이나 끝점으로 하는 빔도 함께 사라진다. 탈출에 필요한 발생기 제거 개수의 최솟값을 구하라. BaoBao가 특정 방향으로 움직일 필요는 없으며, 필요하다면 탈출 경로는 곡선이어도 된다.

테스트 케이스는 여러 개 주어진다. 첫 줄에 테스트 케이스 수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에 레이저 발생기 수 $n$ ($1 \le n \le 10^6$)이 주어진다. 다음 $n$개 줄에는 $i$번째 발생기의 위치 $x_i$, $y_i$ ($-10^9 \le x_i, y_i \le 10^9$)가 주어진다.

발생기의 위치는 모두 서로 다르며, 어떤 레이저 빔이나 발생기도 $(0, 0)$에 닿지 않는다. 모든 테스트 케이스의 $n$을 합하면 $10^6$을 넘지 않는다.

각 테스트 케이스마다 제거해야 하는 발생기 수의 최솟값을 한 줄에 출력한다.

두 번째와 세 번째 테스트 케이스의 그림은 아래와 같다. 채워진 점과 실선은 남은 발생기와 빔이고, 빈 점과 점선은 제거된 발생기와 빔이다. 화살표는 탈출 경로이다.