지뢰밭 탈출

낙하산 강하에 실패한 존스 중위와 그의 소대는 목표 좌표가 아닌 적 지뢰밭 한가운데에 떨어지고 말았다.

존스는 모든 지뢰의 위치가 정확히 표시된 지도를 가지고 있다. 각 대인 지뢰의 폭발 및 감지 반경은 $2$미터이다. 즉, 어떤 지뢰로부터 $2$미터 이내로 들어간 사람은 즉시 사망한다.

지금 소대는 존스가 있는 위치의 덤불 아래에 숨어 안전하다. 이들은 하나의 원형 대형으로 탈출하려 한다. 원형 대형이란 덤불을 중심으로 하는 반지름 $r$의 원판이다. 병사 한 명은 평균 $1$제곱미터의 넓이를 차지하므로, 반지름 $r$의 대형에는 $\lfloor \pi r^2 \rfloor$명의 병사가 들어갈 수 있다.

대형은 언제나 모든 지뢰의 폭발 반경 밖에 있어야 한다. 즉,

• 출발하는 시점에, 덤불을 중심으로 하는 원판 전체가 모든 지뢰로부터 $2$미터 이상 떨어져 있어야 한다.
• 탈출하려면 이 원판이 덤불에서 지뢰밭 바깥까지 이동할 수 있어야 하며, 이동하는 매 순간 원판의 어떤 점도 지뢰로부터 $2$미터 이내로 들어가서는 안 된다(원판은 지뢰 사이의 틈을 통과해야 한다).

존스는 가능한 한 많은 병사를 데리고 나가고 싶어 한다. 안전하게 탈출할 수 있는 가장 큰 대형에 들어가지 못하는 병사는 그 자리에 남겨져 포로가 된다. 탈출할 수 있는 병사의 최대 수를 구하여라.

첫째 줄에 테스트 케이스의 수를 나타내는 양의 정수 $T$가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

• 한 줄에 지뢰의 수를 나타내는 양의 정수 $n$ ($1 \le n < 10^5$)이 주어진다.
• 이어서 $n$개의 줄에 각 지뢰의 좌표를 나타내는 두 정수 $x$, $y$ ($|x|, |y| < 10^5$)가 주어진다. 좌표는 존스의 위치를 기준으로 한 미터 단위의 값이며, 덤불은 원점에 있다. 같은 좌표를 갖는 두 지뢰는 없다.

각 테스트 케이스마다 탈출할 수 있는 병사의 최대 수를 정수 하나로 한 줄에 출력한다.