numeric-game

Rahul and Rohit are playing a game. Initially, two positive integers A and B are written on a blackboard. The players take turns, starting with Rahul. 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.

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

Rahul replaces 51 with 51 - 3*12 = 15, leaving (12, 15) on the blackboard.

Rohit replaces 15 with 15 - 1*12 = 3, leaving (12, 3) on the blackboard.

Rahul replaces 12 with 12 - 3*3 = 3, leaving (3, 3) on the blackboard.

Rohit replaces one 3 with 3 - 1*3 = 0, and loses.

We will say (A, B) is a winning position if Rahul can always win a game that starts with (A, B) on the blackboard, no matter what Rohit does.

Given four integers A1, A2, B1, B2, count how many winning positions (A, B) there are with A1 ≤ A ≤ A2 and B1 ≤ B ≤ B2.

SAMPLE INPUT
1
5 5 8 8

SAMPLE OUTPUT
Case #1: 0

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: