픽셀화된 원

일반적인 컴퓨터 이미지는 픽셀의 행렬이며, 각 픽셀은 특정 색의 작은 정사각형이다. 픽셀 행렬의 축과 완벽하게 평행하지 않은 선을 그리면 결함이 생긴다. 원을 그리는 것은 이러한 결함이 발생하는 극단적인 예이다.

$2\mathbf{R}+1$ × $2\mathbf{R}+1$ 픽셀로 이루어진 그림이 있고, 픽셀의 행과 열에 $-\mathbf{R}$부터 $\mathbf{R}$까지 번호를 매겨 중앙 픽셀이 $0$행 $0$열에 있다고 하자. 처음에는 모든 픽셀이 흰색이다. 그러면 반지름이 $\mathbf{R}$이고 그림의 중앙에 중심이 있는 원을 다음 의사 코드로 검은색으로 그릴 수 있다. 여기서 set_pixel_to_black(x, y)은 $x$행 $y$열의 픽셀을 검은색으로 칠한다.

draw_circle_perimeter(R):
  for x between -R and R, inclusive {
    y = round(sqrt(R * R - x * x))   # round to nearest integer, breaking ties towards zero
    set_pixel_to_black(x, y)
    set_pixel_to_black(x, -y)
    set_pixel_to_black(y, x)
    set_pixel_to_black(-y, x)
  }

코드에 의해 일부 픽셀이 두 번 이상 검은색으로 설정될 수 있지만, 이 연산은 멱등이다(즉, 이미 검은색인 픽셀에 set_pixel_to_black을 호출해도 아무것도 바뀌지 않는다).

다음은 모두 흰색인 그림에서 시작하여 채워진 원을 그리는 함수의 의사 코드이다.

draw_circle_filled(R):
  for x between -R and R, inclusive {
    for y between -R and R, inclusive {
      if round(sqrt(x * x + y * y)) <= R:
        set_pixel_to_black(x, y)
    }
  }

마지막으로, 다음은 채워진 원을 잘못 그리는 의사 코드이다.

draw_circle_filled_wrong(R):
  for r between 0 and R, inclusive {
    draw_circle_perimeter(r)
  }

$\mathbf{R}$이 주어질 때, draw_circle_filled($\mathbf{R}$)을 호출한 그림과 draw_circle_filled_wrong($\mathbf{R}$)을 호출한 또 다른 그림에서 색이 서로 다른 픽셀의 수를 계산하라.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$.

테스트 세트 1 (Visible Verdict)

시간 제한: 10초. $1 \le \mathbf{R} \le 100$.

테스트 세트 2 (Hidden Verdict)

시간 제한: 15초. $1 \le \mathbf{R} \le 10^5$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 그릴 원의 반지름인 하나의 정수 $\mathbf{R}$를 포함하는 한 줄로 설명된다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이고, $y$은 draw_circle_filled($\mathbf{R}$)을 호출한 그림과 draw_circle_filled_wrong($\mathbf{R}$)을 호출한 또 다른 그림에서 색이 서로 다른 픽셀의 수이다.

예제 케이스 #1에서 draw_circle_filled(2)을 호출하면 21개의 픽셀이 검은색으로 그려진다(왼쪽 그림에 표시됨). draw_circle_filled_wrong(2)을 호출하면 17개의 픽셀이 검은색으로 그려진다(오른쪽 그림에 표시됨). 두 그림에서 색이 서로 다른 픽셀은 네 개로, $(-1, -1)$, $(-1, 1)$, $(1, -1)$, $(1, 1)$이다. 여기서 $(x, y)$은 문제 설명에 나온 방식으로 행과 열에 번호를 매겼을 때 $x$행 $y$열의 픽셀을 나타낸다.

예제 케이스 #2에서 다음 그림들은 각각 draw_circle_filled(8)을 호출해 생성한 이미지(왼쪽)와 draw_circle_filled_wrong(8)을 호출해 생성한 이미지(오른쪽)이다.