Mr. Panda has recently fallen in love with a new game called Square Off, in which players compete to find as many different squares as possible on an evenly spaced rectangular grid of dots. To find a square, a player must identify four dots that form the vertices of a square. Each side of the square must have the same length, of course, but it does not matter what that length is, and the square does not necessarily need to be aligned with the axes of the grid. The player earns one point for every different square found in this way. Two squares are different if and only if their sets of four dots are different.

Mr. Panda has just been given a grid with **R** rows and **C** columns of dots. How many different squares can he find in this grid? Since the number might be very large, please output the answer modulo 10^{9} + 7 (1000000007).

The first line of the input gives the number of test cases, **T**. **T** lines follow. Each line has two integers **R** and **C**: the number of dots in each row and column of the grid, respectively.

For each test case, output one line containing `Case #x: y`

, where `x`

is the test case number (starting from 1) and `y`

is the number of different squares can be found in the grid.

1 ≤ **T** ≤ 100.

Time limit: 20 seconds per test set.

Memory limit: 1GB.

2 ≤ **R** ≤ 1000.

2 ≤ **C** ≤ 1000.

2 ≤ **R** ≤ 10^{9}.

2 ≤ **C** ≤ 10^{9}.

Sample Input

4 2 4 3 4 4 4 1000 500

Sample Output

Case #1: 3 Case #2: 10 Case #3: 20 Case #4: 624937395

The pictures below illustrate the grids from the three sample cases and a valid square in the third sample case.

Alice likes reading and buys a lot of books. She stores her books in two boxes; each box is labeled with a pattern that matches the titles of all of the books stored in that box. A pattern consists of only uppercase/lowercase English alphabet letters and stars (`*`

). A star can match between zero and four letters. For example, books with the titles `GoneGirl`

and `GoneTomorrow`

can be put in a box with the pattern `Gone**`

, but books with the titles `TheGoneGirl`

, `Gonetomorrow`

, and `GoneWithTheWind`

cannot.

Alice is wondering whether there is any book that could be stored in either of the boxes. That is, she wonders if there is a title that matches both boxes' patterns.

The first line of the input gives the number of test cases, **T**. **T** test cases follow. Each consists of two lines; each line has one string in which each character is either an uppercase/lowercase English letter or `*`

.

For each test case, output one line containing `Case #x: y`

, where `x`

is the test case number (starting from 1) and `y`

is `TRUE`

if there is a string that matches both patterns, or `FALSE`

if not.

1 ≤ **T** ≤ 50.

Memory limit: 1GB.

Time limit: 20 seconds.

1 ≤ the length of each pattern ≤ 200.

Each pattern contains at most 5 stars.

Time limit: 40 seconds.

1 ≤ the length of each pattern ≤ 2000.

Sample Input

3 **** It Shakes*e S*speare Shakes*e *peare

Sample Output

Case #1: TRUE Case #2: TRUE Case #3: FALSE

In sample case #1, the title `It`

matches both patterns. Note that it is possible for a `*`

to match zero characters.

In sample case #2, the title `Shakespeare`

matches both patterns.

In sample case #3, there is no title that matches both patterns. `Shakespeare`

, for example, does not work because the `*`

at the start of the `*peare`

pattern cannot match six letters.

"Look at the stars, look how they shine for you." - Coldplay, "Yellow"

In a galaxy far, far away, there are many stars. Each one is a sphere with a certain position (in three-dimensional space) and radius. It is possible for stars to overlap each other.

The stars are so incredibly beautiful to you that you want to capture them forever! You would like
to build two cubes of the same integer edge length, and place them in space such that for each
star, there is at least one cube that *completely* contains it. (It's not enough for a star
to be completely contained by the union of the two cubes.) A star is completely contained by a
cube if no point on the star is outside the cube; a point exactly on a cube face is still
considered to be inside the cube.

The cubes can be placed anywhere in space, but they must be placed with their edges parallel to the coordinate axes. It is acceptable for the cubes to overlap stars or each other.

What is the minimum integer edge length that allows you to achieve this goal?

The input starts with one line containing exactly one integer **T**, which is the number of
test cases. **T** test cases follow.

Each test case begins with a line containing an integer, **N**, representing the number of
stars.

This is followed by **N** lines. On the ith line, there are 4 space-separated integers,
**X _{i}**,

For each test case, output one line containing `Case #x: y`

, where `x`

is
the test case number (starting from 1) and `y`

is the minimum cube edge length that
solves the problem, as described above.

Time limit: 20 seconds per test set.

Memory limit: 1GB.

-10

-10

-10

1 ≤

Sample Input

3 3 1 1 1 1 2 2 2 1 4 4 4 1 3 1 1 1 2 2 3 4 1 5 6 7 1 3 1 1 1 1 1 1 1 1 9 9 9 1

Sample Output

Case #1: 3 Case #2: 5 Case #3: 2

In the first test case, one solution is to place two cubes with an edge length of 3 such that
their corners with minimum (x, y, z) coordinates are at (0, 0, 0) and (3, 3, 3).

In the second test case, one solution is to place two cubes with an edge length of 5 such that
their corners with minimum (x, y, z) coordinates are at (-1, -1, -1) and (1, 2, 3).

Test Data

We recommend that you practice debugging solutions without looking at the test data.

Test Data

We recommend that you practice debugging solutions without looking at the test data.

Test Data

We recommend that you practice debugging solutions without looking at the test data.