You know one of the most dangerous villain of all time, it's Darth Vader. It's time to stop him and Master Luke is looking forward to fight against him. They both are in an infinite two-dimensional grid. Each cell is denoted by (x, y). Here x denotes the row number and y denotes the column number of that cell. Please have a look on that picture of 5 * 7 grid to understand.

Luke stays at a cell (x1, y1) and Vader stays at another cell (x2, y2). It is guaranteed that x1 <= x2 and y1 <= y2. Master Luke needs to reach Vader’s cell. Each time Luke can move one step below horizontally or vertically or diagonally. That means, if his position is (x, y) then he can move to (x+1, y) or (x, y+1) or (x+1, y+1) cell in a single move. Given Luke and Vader’s position you have to determine in how many ways Luke can reach to the Vader’s cell. As the answer can be very large output the solution modulo 10^9 + 7.

Input

Input starts with an integer (T <= 50) which denotes the number of test case. Each test case consists four integer x1, y1, x2, y2 (0 <= x1 <= x2 <= 100000 and 0 <= y1 <= y2 <= 100000), the position of Luke and Vader.

Output

For each test case, print the number of ways Luke can reach to the Vader’s cell modulo 10^9 + 7.

Example

Input:
3
1 2 2 3
2 2 3 3
3 4 3 5

Output:
Case 1: 3
Case 2: 3
Case 3: 1

Explanation

In the first case he can move from (1, 2) to (2, 3) in the following 3 ways:

• (1, 2) → (1, 3) → (2, 3)
• (1, 2) → (2, 2) → (2, 3)
• (1, 2) → (2, 3)