기둥 갤러리 (Small)

친구 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 300$

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

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