NUMGAME - Number Game

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*B for any positive integer k, or replace B with B - k*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*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 A1, A2, B1, B2, count how many winning positions (A, B) there are with A1AA2 and B1BB2.

Input

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 A1, A2, B1, B2, separated by spaces.

1 ≤ T ≤ 250.
1 ≤ A1A2 ≤ 1,000,000.
1 ≤ B1B2 ≤ 1,000,000.
A2 - A1 ≤ 999,999.
B2 - B1 ≤ 999,999.

Output

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 A1AA2 and B1BB2.

Example

Input:
3
5 5 8 8
11 11 2 2
1 6 1 6 Output: Case #1: 0
Case #2: 1
Case #3: 20

Added by:Mohammad Kotb
Date:2010-09-03
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: OBJC VB.NET
Resource:Code Jam 2010

hide comments
2022-08-20 14:43:44
HINT : Golden Ratio

Some Testcases :

7
1 999 333 666
1 333 666 999
1 777 333 999
333 5555 77777 999999
555 3333 99999 777777
333 999999 7777 99999
7 777777 9 999999

Case #1: 168757
Case #2: 111222
Case #3: 291936
Case #4: 4816770729
Case #5: 1883547841
Case #6: 87222576717
Case #7: 495939647292

Last edit: 2022-08-20 14:50:29
2010-09-13 20:55:46 Amlesh Jayakumar
Shouldn't O(T*max(b2-b1, a2-a1)) be sufficient for the given Time Limit? I am constantly TLE'ing...even though I am pretty sure I am getting the methodology right..
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.