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