기둥 갤러리

여러분의 친구 Cody-Jamal은 "기둥 갤러리"라는 새로운 예술 설치 작품을 작업하고 있다. 이 설치 작품은 가로와 세로가 각각 N미터인 정사각형 갤러리에 전시될 예정이다. 갤러리는 1미터 × 1미터 크기의 정사각형 $N^{2}$개로 나뉘어 N × N 행렬을 이룬다. 남서쪽 모서리 칸의 정확한 중심을 관찰 지점이라고 하며, 작품을 관람하는 사람은 그곳에 서 있어야 한다. 나머지 각 칸에는 원기둥 모양의 기둥이 하나씩 있다. 모든 기둥에는 반지름이 R인 원형 밑면이 두 개 있다. 하나는 해당 칸의 중심에 놓인 채 바닥에 닿아 있고, 다른 하나는 갤러리의 천장에 닿아 있다. 관찰자는 관찰 지점에 서서 $N^{2}$ - 1개의 기둥을 바라보며 감탄할 것이다.

Cody-Jamal은 현재 N의 값을 얼마나 크게 할 수 있는지 알아보기 위해 장소를 물색하고 있다. 또한 기둥을 어떤 재료로 만들지도 아직 결정하지 않았다. 콘크리트일 수도 있고 탄소 나노튜브일 수도 있으므로, 각 기둥 밑면의 반지름 R은 1마이크로미터부터 거의 반 미터까지 달라질 수 있다. 반지름이 반 미터이면 이웃한 기둥끼리 맞닿는다는 점에 유의하라.

훈련받은 수학자인 여러분은 관찰 지점에서 볼 수 없는 기둥이 있을 수 있음을 금방 알아차린다. Cody-Jamal은 여러 N과 R의 조합에 대해 보이는 기둥의 수를 구할 수 있도록 여러분에게 도움을 요청한다. 엄밀히 말해, 남서쪽 모서리 칸의 중심(관찰 지점)에서 기둥 경계의 임의의 한 점까지 이어지고 다른 어떤 기둥에도 닿거나 다른 어떤 기둥과도 교차하지 않는 직선 선분이 존재할 때, 그리고 그럴 때에만 그 기둥은 보인다.

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ R < $10^{6}$ / 2.

작은 데이터 세트(테스트 세트 1 - 공개)

2 ≤ N ≤ 300.

큰 데이터 세트(테스트 세트 2 - 비공개)

2 ≤ N ≤ $10^{9}$.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 줄은 서로 다른 테스트 케이스를 나타내며 두 정수 N과 R이 주어진다. N은 갤러리의 각 차원을 따라 배치된 한 변의 길이가 1미터인 정사각형 칸의 수이고, R은 마이크로미터 단위로 나타낸 각 기둥의 반지름이다. 따라서 각 기둥의 반지름을 미터 단위로 나타내면 R / $10^{6}$이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 설치 작품의 기둥 중 관찰 지점에서 보이는 기둥의 수이다.

아래 그림은 처음 두 예제를 보여 준다(실제 비율과 다름). 검은색 원의 중심에는 관찰자가 있다. 나머지 원은 기둥이며, 보이는 기둥은 회색으로, 보이지 않는 기둥은 빨간색으로 표시되어 있다. 파란색 점선은 가로막히지 않은 시선 중 일부를 나타내고, 빨간색 점선은 가로막힌 시선을 나타낸다(처음으로 가로막히는 지점부터 회색으로 바뀐다).