Raj is fond of Table Tennis. He has a few friends who also play table tennis. Once as he walked past his college, he found 2 of his friends, Melvin and Rakesh playing.

Anyone who plays Table Tennis, knows that when player p1 and p2 play a game of TT, the general scoring scheme is of the form,"p1:p2" where p1 is the score of the player 1 and p2 is that of player 2. The game starts at 0:0. When player 1 scores a point, the score becomes p1+1:p2. If from p1:p2, player 2 had scored a point, the score would become p1:p2+1.The game ends when either of them reaches a score of atleast 11 and the difference in score of the 2 players is exactly 2. The players stop playing when the game ends.

As he walked past the scoreboard, he found the scores to be : "X1:Y1". Raj then decides to play a game too. So, he rushes to his room to put on some casual clothing and join the two. When he returns back, he found that the game had ended and the scores then were: X2:Y2.

Since both Melvin and Rakesh are equally good, the match could have gone on a few duece before ending.
We say the scores are at duece, when the score of the two players is greater than or equal to 10 and the difference in their score is 0 at that instant.

Now Melvin, being a big fan of maths, makes a condition that Raj can join them in playing TT, if he answers his question correctly. Melvin goes on to state his question.

"Going by the normal rules of TT, in how many possible ways, the score X1:Y1 could have been converted to X2:Y2?"

Two scoring ways are said to be different, if the scoreboard is different after any Kth point was scored in the match.
(Obviously, (x1+y1 ≤ K ≤ x2+y2))

Raj is desperate to get a game and he is in no mood to squeeze his brain to answer Melvin. So, he calls you to help him.

So, given the initial score X1:Y1 and the final score X2:Y2, print the number of ways in which the initial score could have been converted to the final score. Melvin is tricky, and so he may even give wrong scores. So, if X2:Y2 is not a valid final score, print -1.

A valid final score is one which is reachable from the initial score and at which the game has ended.

Input:
The first line contains an integer T, denoting the number of testcases to come.
Then each of the next T lines contain 4 integers: x1, y1, x2, y2 separated by spaces.
where (x1,y1) denotes the initial score and (x2,y2) denotes the final score.

Output:
For each Testcase 'i', print on a new line, Case i: x
where x is the number of ways to achieve the scoring OR "-1" if X2:Y2 is not a valid final score. (Quotes for clarity)
Since the value can be large, output it modulo 1000000009.

Constraints:
1 ≤ T ≤ 100
0 ≤ x1 ≤ x2 ≤ 30
0 ≤ y1 ≤ y2 ≤ 30

SAMPLE INPUT
2
6 9 11 9
10 11 14 12

SAMPLE OUTPUT
Case 1: 1
Case 2: 2

Explanation

In Case 1:
Player 2 didn't get any additional points. All the points after the initial scores were scored by player 1. There is only one possible way for that.

In Case 2:
From, 10:11, the score could not have gone to 10:12, because that would end the game. So, the next score should have been 11:11.From 11, 11, either p1 or p2 could have scored, leading to:
12 11 (or) 11 12.
If the score had been 11, 12, then the next 3 points were scored by p1. This gives us one way of reaching 14:12.
If the score had been 12 11, the next score should have been 12 12
** (Because, if the score had become 13:11, then the game would have ended)**
From 12:12, the next 2 points must have been scored by P1, leading to 14:12. This gives another way of reaching 14:12.
Thus the 2 ways are:
10:11 -> 11:11-> 12:11-> 12:12-> 13:12 ->14:12
10:11 -> 11:11-> 11:12-> 12:12-> 13:12-> 14:12

The two ways are different because the scoreboard is different when the 23rd point was scored in the match (12:11 and 11:12)
Thus the answer is 2.

见题面

见题面