기둥 갤러리 (Large)

친구 Cody-Jamal이 "기둥 갤러리"라는 새 설치 미술 작품을 준비하고 있다. 이 작품은 가로세로 $N$미터인 정사각형 갤러리에 전시된다. 갤러리는 $1 \times 1$미터 칸 $N^2$개로 나뉘어 $N \times N$ 격자를 이룬다. 남서쪽 모서리 칸의 정중앙을 관람 지점이라고 부르며, 작품을 보는 사람은 이곳에 선다. 나머지 칸에는 원기둥 모양의 기둥이 하나씩 있다. 모든 기둥은 반지름이 $R$인 원형 밑면 두 개로 이루어지며, 한 밑면은 해당 칸의 중앙에 놓여 바닥에 닿고 다른 밑면은 갤러리 천장에 닿는다. 관람객은 관람 지점에 서서 $N^2 - 1$개의 기둥을 바라보며 감탄한다.

Cody-Jamal은 지금 전시 장소를 물색하며 $N$을 얼마나 크게 할 수 있을지 알아보고 있다. 기둥 재료도 아직 정하지 않았다. 콘크리트일 수도 있고 탄소 나노튜브일 수도 있으므로 기둥 밑면의 반지름 $R$은 1마이크로미터부터 0.5미터 가까이까지 달라질 수 있다. 반지름이 정확히 0.5미터라면 이웃한 기둥끼리 맞닿는다는 점에 주의하자.

수학을 공부한 여러분은 관람 지점에서 보이지 않는 기둥이 있을 수 있다는 사실을 금방 알아챘다. Cody-Jamal은 여러 $N$과 $R$의 조합에 대해 보이는 기둥의 개수를 구해 달라고 부탁했다. 엄밀하게 말하면, 기둥이 보인다는 것은 남서쪽 모서리 칸의 중앙(관람 지점)에서 그 기둥 경계 위의 어떤 점까지 이어지는 선분 가운데 다른 어떤 기둥에도 닿거나 교차하지 않는 선분이 존재한다는 뜻이다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 줄에 테스트 케이스가 하나씩 주어진다. 각 줄에는 두 정수 $N$과 $R$이 주어진다. $N$은 갤러리 한 변을 따라 놓인 1미터 정사각형 칸의 개수이고, $R$은 각 기둥의 반지름을 마이크로미터 단위로 나타낸 값이다. 즉 각 기둥의 반지름은 미터 단위로 $R / 10^6$이다.

제한

• $1 \le T \le 100$
• $1 \le R < 10^6 / 2$
• $2 \le N \le 10^9$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 관람 지점에서 보이는 기둥의 개수이다.

아래 그림은 첫 두 예제를 나타낸 것이다(실제 비율과는 다르다). 검은 원의 중심에 관람객이 서 있다. 다른 원은 기둥이며, 보이는 기둥은 회색, 보이지 않는 기둥은 빨간색이다. 파란 점선은 가로막히지 않은 시선의 일부를 나타낸다. 빨간 점선은 가로막힌 시선이며, 처음 가로막히는 지점부터 회색으로 바뀐다.