BUET Inter-University Programming Contest

Problem D – Donkey of the sultan

Problem

Finally our sultan got married. There were varieties of gifts in the wedding- gold, silver, diamond, platinum, elephant, horse, silk clothes etc. Among all gifts one gift was different from all the others. That is donkey. Though its name was donkey but it was very intelligent. Because of this donkey he won many battles without any bloodshed. How? The donkey was expert of game theory. So the sultan took the donkey with him to the country which he wished to conquer and proposed for a game.

The game is played with 1 gold coin, 1 diamond coin and 1 silver coin. The game is played in a long strip (It is really very very long).

First the opponent of sultan will get the opportunity to place the coins in the strip. Leftmost coin should be gold, then diamond and rightmost is silver. But the opponent has to follow some constraints given by the sultan. Sultan says:

1. There should be at least a1 and at most a2 cells between left end point of the strip and gold coin.

2. There should be at least b1 and at most b2 cells between gold and diamond coin.

3. There should be at least c1 and at most c2 cells between diamond and silver coin.

At each move a player may move one of the three coins to the adjacent cell to its left OR move both the gold and silver coins to the adjacent cell to its left. After movement no cell should contain more than one coin. Coins may not be moved beyond the left end of the strip. The game finishes when no player can move.

The sultan came to your country now and wants to play with you. He has given the numbers a₁, a₂, b₁, b₂, c₁ and c₂. You will place the coins in the strip. Then the sultan will give his move, then you will move, then again sultan and so on. You have to calculate the number of position you can start with following the Sultan’s constraint so that you can win the game. Assume that both of you will play optimally. Two positions will be different if the placement of any of the coins is different.

Input

In the first line of there will be number of test case T . Each of the following T lines contains a₁, a₂, b₁, b₂, c₁ and c₂ .

Output

For each test case output the case number followed by the number of winning positions. For specific format please follow the sample input output.

Sample Input	Output for Sample Input
2 1 1 0 0 1 1 2 3 1 1 3 4	Case 1: 0 Case 2: 1

Explanation of 1^st Sample

The given sample results in only one possible starting position that is:

G

D

S

This is a losing position for you, because in the first move the sultan will move both Gold and Silver coins. Then you have no other way but moving Diamond coin. Then sultan will move Silver coin and you don’t have any move. So, you lose.

Problemsetter:	Md. Mahbubul Hasan
Special Thanks:	Tasnim Imran Sunny