题目描述

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$.

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

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

提示

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.