Arya and Bran are playing a game. Initially, two positive integers and
are written on a blackboard. The players take turns, starting with Arya. On his or her turn, a player can replace
with
for any positive integer
, or replace
with
for any positive integer
. The first person to make one of the numbers drop to zero or below loses.
For example, if the numbers are initially , the game might progress as follows:
- Arya replaces
with
, leaving
on the blackboard.
- Bran replaces
with
, leaving
on the blackboard.
- Arya replaces
with
, leaving
on the blackboard.
- Bran replaces one
with
, and loses.
We will say is a winning position if Arya can always win a game that starts with
on the blackboard, no matter what Bran does.
Given four integers ,
,
,
, count how many winning positions
there are with
and
.
Input Specification
The first line of the input gives the number of test cases, .
test cases follow, one per line. Each line contains the four integers
,
,
,
, separated by spaces.
Output Specification
For each test case, output one line containing Case #x: y
, where is the case number (starting from 1), and
is the number of winning positions
with
and
.
Limits
Memory limit: 1 GB.
.
.
.
Small Dataset
Time limit: 30 seconds.
.
.
Large Dataset
Time limit: 90 seconds.
.
.
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.
Comments