힐베르트 곡선

힐베르트 곡선은 독일 수학자 다비트 힐베르트가 처음 소개한, 연속이면서 공간을 가득 채우는 프랙탈 곡선이다.

이 곡선은 가로 선분과 세로 선분으로 이루어진 곡선의 수열 $H_1, H_2, H_3, \dots$ 로 정의한다. 각 곡선은 단위 정사각형 $[0, 1] \times [0, 1]$ 안에 놓인다.

$H_1$ 은 네 점 $(\frac{1}{4}, \frac{3}{4})$, $(\frac{1}{4}, \frac{1}{4})$, $(\frac{3}{4}, \frac{1}{4})$, $(\frac{3}{4}, \frac{3}{4})$ 을 차례로 잇는 세 선분으로 이루어진다.

$H_n$ 은 $H_{n-1}$ 로부터 다음 네 단계를 거쳐 재귀적으로 만든다.

1. $H_{n-1}$ 의 모든 좌표를 절반으로 줄인다.
2. 그 곡선을 점 $(0, \frac{1}{2})$ 을 중심으로 반시계 방향으로 $90^\circ$ 돌린 곡선을 추가한다.
3. 지금까지 만든 곡선을 직선 $x = \frac{1}{2}$ 에 대하여 대칭시킨 곡선을 추가한다.
4. $m = \frac{1}{2^{n+1}}$ 이라 하자. 각 조각의 끝점들을 세 선분으로 잇는다. 즉, $(\frac{1}{2} - m, \frac{1}{2} - m)$ 과 $(\frac{1}{2} + m, \frac{1}{2} - m)$ 을, $(m, \frac{1}{2} - m)$ 과 $(m, \frac{1}{2} + m)$ 을, $(1 - m, \frac{1}{2} - m)$ 과 $(1 - m, \frac{1}{2} + m)$ 을 각각 잇는다.

수평 선분이 주어졌을 때, 이 곡선과 만나는 교점의 개수를 구하는 프로그램을 작성하라. 예를 들어 $H_3$ 과 수평 선분 $(\frac{2}{8}, \frac{7}{8})$–$(\frac{7}{8}, \frac{7}{8})$ 은 $3$ 개의 점에서 만나고, $H_4$ 와 수평 선분 $(\frac{0}{16}, \frac{1}{16})$–$(\frac{16}{16}, \frac{1}{16})$ 은 $16$ 개의 점에서 만난다.

$H_n$ 의 꼭짓점 좌표는 항상 $\frac{1}{2^{n+1}}$ 의 홀수 배수이고, 수평 선분 끝점의 좌표는 항상 $\frac{1}{2^{n}}$ 의 배수이다. 따라서 수평 선분은 항상 $H_n$ 의 세로 선분 부분과만 만난다.

입력은 여러 개의 데이터(테스트 케이스)로 이루어지며, 데이터는 최대 $100$ 개이다.

각 데이터는 공백으로 구분된 네 정수 $n$, $x_1$, $x_2$, $y$ 로 주어진다. 이는 곡선 $H_n$ 과 수평 선분 $(\frac{x_1}{2^n}, \frac{y}{2^n})$–$(\frac{x_2}{2^n}, \frac{y}{2^n})$ 을 나타낸다. $0 < n < 31$, $x_1 < x_2$ 이며, $x_1$, $x_2$, $y$ 는 모두 $[0, 2^n]$ 범위의 정수이다.

마지막 데이터 다음 줄에는 $0$ 이 하나 주어지며, 이는 입력의 끝을 뜻한다.

각 데이터에 대하여 곡선 $H_n$ 과 주어진 수평 선분이 만나는 교점의 개수를 한 줄에 하나씩 출력한다.