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 - kB for any positive integer k, or replace B with B - kA for any positive integer k. The first person to make one of the numbers drop to zero or below loses.</p>

For example, if the numbers are initially (12, 51), the game might progress as follows:

• Arya replaces 51 with 51 - 3*12 = 15, leaving (12, 15) on the blackboard.
• Bran replaces 15 with 15 - 1*12 = 3, leaving (12, 3) on the blackboard.
• Arya replaces 12 with 12 - 3*3 = 3, leaving (3, 3) on the blackboard.
• Bran replaces one 3 with 3 - 1*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₁, A₂, B₁, B₂, count how many winning positions (A, B) there are with A₁ ≤ A ≤ A₂ and B₁ ≤ B ≤ B₂.

입력 형식

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₁, A₂, B₁, B₂, separated by spaces.</p>

Limits

• 1 ≤ T ≤ 100. 
• 1 ≤ A₁ ≤ A₂ ≤ 1,000,000.
• 1 ≤ B₁ ≤ B₂ ≤ 1,000,000.
• A₂ - A₁ ≤ 999,999.
• B₂ - B₁ ≤ 999,999.

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₁ ≤ A ≤ A₂ and B₁≤ B ≤ B₂.

예제 입력

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

예제 출력

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