Number Game (Small)

Arya and Bran play a game. At the start, two positive integers $A$ and $B$ are written on a blackboard. The players move in turns and Arya moves first. On a turn, a player picks a positive integer $k$ and either replaces $A$ with $A - k \times B$, or replaces $B$ with $B - k \times A$. Whoever first makes one of the two numbers drop to zero or below loses.

For example, if the numbers start at $(12, 51)$, the game can go like this.

• Arya replaces 51 with $51 - 3 \times 12 = 15$, so the blackboard holds $(12, 15)$.
• Bran replaces 15 with $15 - 1 \times 12 = 3$, so the blackboard holds $(12, 3)$.
• Arya replaces 12 with $12 - 3 \times 3 = 3$, so the blackboard holds $(3, 3)$.
• Bran replaces one of the 3s with $3 - 1 \times 3 = 0$ and loses.

Call a starting position $(A, B)$ a winning position if Arya can always win from it, whatever Bran does.

Given four integers $A_1$, $A_2$, $B_1$, $B_2$, count the winning positions $(A, B)$ with $A_1 \le A \le A_2$ and $B_1 \le B \le B_2$.

The first line holds the number of test cases $T$. Each of the next $T$ lines holds four integers $A_1$, $A_2$, $B_1$, $B_2$ separated by spaces.

Limits

• $1 \le T \le 100$
• $1 \le A_1 \le A_2 \le 1{,}000{,}000$
• $1 \le B_1 \le B_2 \le 1{,}000{,}000$
• $A_2 - A_1 \le 30$
• $B_2 - B_1 \le 30$

For each test case, print one line in the form Case #x: y. Here $x$ is the test case number starting from 1, and $y$ is the number of winning positions $(A, B)$ with $A_1 \le A \le A_2$ and $B_1 \le B \le B_2$.