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\cdot B$ for any positive integer $k$, or replace $B$ with $B-k\cdot 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\ast 12=15$, leaving $(12,15)$ on the blackboard.
• Bran replaces $15$ with $15-1\ast 12=3$, leaving $(12,3)$ on the blackboard.
• Arya replaces $12$ with $12-3\ast 3=3$, leaving $(3,3)$ on the blackboard.
• Bran replaces one $3$ with $3-1\ast 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\le A\le A_2$ and $B_1\le B\le B_2$.

Input Specification

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.

Output Specification

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\le A\le A_2$ and $B_1\le B\le B_2$.

Limits

Memory limit: 1 GB.

$1\le T\le 100$.

$1\le A_1\le A_2\le 1000000$.

$1\le B_1\le B_2\le 1000000$.

Small Dataset

Time limit: 30 seconds.

$A_2-A_1\le 30$.

$B_2-B_1\le 30$.

Large Dataset

Time limit: 90 seconds.

$A_2-A_1\le 999999$.

$B_2-B_1\le 999999$.

No additional constraints.

Sample Input

3
5 5 8 8
11 11 2 2
1 6 1 6

Sample Output

Case #1: 0
Case #2: 1
Case #3: 20

Note

This problem has different time limits for different batches. If you exceed the Time Limit for any batch, the judge will incorrectly display >90.000s regardless of the actual time taken. Refer to the Limits section for batch-specific time limits.