Number Game

Arya and Bran play a game. A blackboard starts with two positive integers $A$ and $B$ written on it. The players take turns and Arya goes first. On a turn a player picks a positive integer $k$ and replaces $A$ with $A - k \times B$, or replaces $B$ with $B - k \times A$. The player who makes one of the two numbers drop to zero or below loses.

If the numbers start at $(12, 51)$, one possible game runs like this.

• 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)$.
• Arya replaces 12 with $12 - 3 \times 3 = 3$, leaving $(3, 3)$.
• Bran replaces one 3 with $3 - 1 \times 3 = 0$ and loses.

Call $(A, B)$ a winning position when Arya wins every game that starts from it, no matter how Bran plays.

You are 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 contains the number of test cases $T$. Each of the next $T$ lines holds one test case: the 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 10^6$
• $1 \le B_1 \le B_2 \le 10^6$

For each test case print one line of the form 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 \le A \le A_2$ and $B_1 \le B \le B_2$.