MATCITY - Matrix City

no tags 

Ahmed Hussein often goes to his friend Osama who lives in the Matrix City, the Matrix City is designed to have square shaped buildings and streets and avenues crossing between them horizontally and vertically making it to look like a Matrix.

In the Matrix City, the Sun only rises in the South West (Strange, isn’t it?) so Ahmed can only walk with his back to the sun facing either the North or the East only (because Ahmed Hussein's skin is very sensitive to the sun rays), we know that Osama’s house is always on his North East side.

Unfortunately, Ahmed gets bored easily so every time he visits Osama he chooses a different path to walk than the one he had chosen before and he never walks the same path twice, after that he dumps him and finds another friend to visit, the figure shown illustrates the first test case.

Input

You're given the number of test cases T where (0 < T < 100), for each test case you'll be given current position of Ahmed (x1, y1) and the position of Osama's house (x2, y2) where (0 < x2 - x1 < 10 ), (x1 < x2), (0 < y2 - y1 < 10), (y1 < y2) and (0< (x1, x2, y1, y2) < 2^63).

Output

For each test case print "Case_#i:_X" where "i" is the case number (starting from 1), "X" is the number of different paths/routes Ahmed could choose before he could get bored from visiting Osama again and "_" is a space. The answer for each test case should be printed in separate line.

Example

Input:
2
3 2 8 6
1 1 3 2

Output:
Case #1: 126
Case #2: 3


Added by:Sharaf
Date:2013-02-07
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:2013 acmASCIS Level 1 Contest