Hilbert Curve

The Hilbert curve is a continuous, space-filling fractal curve first described by the German mathematician David Hilbert.

It is defined through a sequence of curves $H_1, H_2, H_3, \dots$, each made of horizontal and vertical segments. Every curve lies inside the unit square $[0, 1] \times [0, 1]$.

$H_1$ consists of the three segments that connect the four points $(\frac{1}{4}, \frac{3}{4})$, $(\frac{1}{4}, \frac{1}{4})$, $(\frac{3}{4}, \frac{1}{4})$, $(\frac{3}{4}, \frac{3}{4})$ in order.

$H_n$ is built recursively from $H_{n-1}$ through the following four steps.

1. Halve every coordinate of $H_{n-1}$.
2. Add a copy of that curve rotated $90^\circ$ counterclockwise about the point $(0, \frac{1}{2})$.
3. Add a copy of the curve obtained so far, reflected across the line $x = \frac{1}{2}$.
4. Let $m = \frac{1}{2^{n+1}}$. Join the pieces with three segments: connect $(\frac{1}{2} - m, \frac{1}{2} - m)$ with $(\frac{1}{2} + m, \frac{1}{2} - m)$, connect $(m, \frac{1}{2} - m)$ with $(m, \frac{1}{2} + m)$, and connect $(1 - m, \frac{1}{2} - m)$ with $(1 - m, \frac{1}{2} + m)$.

Given a horizontal segment, write a program that counts how many points it shares with the curve. For example, $H_3$ meets the horizontal segment $(\frac{2}{8}, \frac{7}{8})$–$(\frac{7}{8}, \frac{7}{8})$ at $3$ points, and $H_4$ meets the horizontal segment $(\frac{0}{16}, \frac{1}{16})$–$(\frac{16}{16}, \frac{1}{16})$ at $16$ points.

The vertex coordinates of $H_n$ are always odd multiples of $\frac{1}{2^{n+1}}$, while the endpoint coordinates of the horizontal segment are always multiples of $\frac{1}{2^{n}}$. Consequently the horizontal segment only ever meets the vertical parts of $H_n$.

The input consists of several datasets (test cases), at most $100$ of them.

Each dataset is given as four space-separated integers $n$, $x_1$, $x_2$, $y$, describing the curve $H_n$ and the horizontal segment $(\frac{x_1}{2^n}, \frac{y}{2^n})$–$(\frac{x_2}{2^n}, \frac{y}{2^n})$. Here $0 < n < 31$ and $x_1 < x_2$, and $x_1$, $x_2$, $y$ are all integers in the range $[0, 2^n]$.

A single line containing $0$ follows the last dataset and marks the end of the input.

For each dataset, print on its own line the number of points where the curve $H_n$ meets the given horizontal segment.