P13392 [GCJ 2010 #1A] Number Game

Arya and Bran are playing a game. Initially, two positive integers $A$ and $B$ are written on a blackboard. The players take turns, starting with Arya. On his or her turn, a player can replace $A$ with $A - k \times B$ for any positive integer $k$, or replace $B$ with $B - k \times A$ for any positive integer $k$. The first person to make one of the numbers drop to zero or below loses. For example, if the numbers are initially $(12, 51)$, the game might progress as follows: - Arya replaces $51$ with $51 - 3 \times 12 = 15$, leaving $(12, 15)$ on the blackboard. - Bran replaces $15$ with $15 - 1 \times 12 = 3$, leaving $(12, 3)$ on the blackboard. - Arya replaces $12$ with $12 - 3 \times 3 = 3$, leaving $(3, 3)$ on the blackboard. - Bran replaces one $3$ with $3 - 1 \times 3 = 0$, and loses. We will say $(A, B)$ is a winning position if Arya can always win a game that starts with $(A, B)$ on the blackboard, no matter what Bran does. Given four integers $A_1$, $A_2$, $B_1$, $B_2$, count how many winning positions $(A, B)$ there are with $A_1 \leq A \leq A_2$ and $B_1 \leq B \leq B_2$.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow, one per line. Each line contains the four integers $A_1$, $A_2$, $B_1$, $B_2$, separated by spaces.

For each test case, output one line containing "Case #x: y", where $x$ is the case number (starting from 1), and $y$ is the number of winning positions $(A, B)$ with $A_1 \leq A \leq A_2$ and $B_1 \leq B \leq B_2$.

**Limits** - $1 \leqslant T \leqslant 100.$ - $1 \leqslant A_1 \leqslant A_2 \leqslant 1,000,000.$ - $1 \leqslant B_1 \leqslant B_2 \leqslant 1,000,000.$ **Small dataset (16 Pts, Test set 1 - Visible)** - Time limit: ~~30~~ 3 seconds. - $A_2 - A_1 \leqslant 30.$ - $B_2 - B_1 \leqslant 30.$ **Large dataset (25 Pts, Test set 2 - Hidden)** - Time limit: ~~90~~ 9 seconds. - $A_2 - A_1 \leqslant 999,999.$ - $B_2 - B_1 \leqslant 999,999.$ - No additional constraints.