The Constitution of a certain country states that the leader is the person with the name containing the greatest number of different alphabet letters. (The country uses the uppercase English alphabet from A through Z.) For example, the name `GOOGLE`

has four different alphabet letters: E, G, L, and O. The name `APAC CODE JAM`

has eight different letters. If the country only consists of these 2 persons, `APAC CODE JAM`

would be the leader.

If there is a tie, the person whose name comes earliest in alphabetical order is the leader.

Given a list of names of the citizens of the country, can you determine who the leader is?

The first line of the input gives the number of test cases, **T**. **T** test cases follow. Each test case starts with a line with an interger **N**, the number of people in the country. Then **N** lines follow. The i-th line represents the name of the i-th person. Each name contains at most 20 characters and contains at least one alphabet letter.

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 name of the leader.

1 ≤ **T** ≤ 100.

Time limit: 20 seconds per test set.

Memory limit: 1GB.

1 ≤ **N** ≤ 100.

Each name consists of at most 20 characters and only consists of the uppercase English letters `A`

through `Z`

.

Each name consists of at most 20 characters and only consists of the uppercase English letters `A`

through `Z`

and ' '(space).

All names start and end with alphabet letters.

Sample Input

2 3 ADAM BOB JOHNSON 2 A AB C DEF

Sample Output

Case #1: JOHNSON Case #2: A AB C

`JOHNSON`

contains 5 different alphabet letters('H', 'J', 'N', 'O', 'S'), so he is the leader.Sample case #2 would only appear in Large data set. The name

`DEF`

contains 3 different alphabet letters, the name `A AB C`

also contains 3 different alphabet letters. `A AB C`

comes alphabetically earlier so he is the leader.
There's an island in the sea. The island can be described as a matrix with **R**
rows and **C** columns, with **H[i][j]** indicating the height of each unit cell.
Following is an example of a 3*3 island:

3 5 5 5 4 5 5 5 5Sometimes, a heavy rain falls evenly on every cell of this island. You can assume that an arbitrarily large amount of water falls. After such a heavy rain, some areas of the island (formed of one or more unit cells joined along edges) might collect water. This can only happen if, wherever a cell in that area shares an edge (not just a corner) with a cell outside of that area, the cell outside of that area has a larger height. (The surrounding sea counts as an infinite grid of cells with height 0.) Otherwise, water will always flow away into one or more of the neighboring areas (for our purposes, it doesn't matter which) and eventually out to sea. You may assume that the height of the sea never changes. We will use W[i][j] to denote the heights of the island's cells after a heavy rain. Here are the heights of the example island after a heavy rain. The cell with initial height 4 only borders cells with higher initial heights, so water will collect in it, raising its height to 5. After that, there are no more areas surrounded by higher cells, so no more water will collect. Again, note that water cannot flow directly between cells that intersect only at their corners; water must flow along shared edges.

Following is the height of the example island after rain:

3 5 5 5 5 5 5 5 5Given the matrix of the island, can you calculate the total increased height sum(W[i][j]-

The first line of the input gives the number of test cases, **T**. **T** test cases follow.

The first line of each test case contains two numbers **R** and **C** indicating the number of rows and columns of cells on the island.
Then, there are **R** lines of **C** positive integers each. The j-th value on the i-th of these lines gives **H[i][j]**: the height of the cell in the i-th row and the j-th column.

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 total increased height.

1 ≤ **T** ≤ 100.

Time limit: 30 seconds per test set.

Memory limit: 1GB.

1 ≤ **H[i][j]** ≤ 1000.

1 ≤ **R** ≤ 10.

1 ≤ **C** ≤ 10.

1 ≤ **R** ≤ 50.

1 ≤ **C** ≤ 50.

Sample Input

3 3 3 3 5 5 5 4 5 5 5 5 4 4 5 5 5 1 5 1 1 5 5 1 5 5 5 2 5 8 4 3 2 2 2 2 1 2 2 1 2 2 1 2

Sample Output

Case #1: 1 Case #2: 3 Case #3: 0

Case 1 is explained in the statement.

In case 2, the island looks like this after the rain:

5 5 5 1 5 2 2 5 5 2 5 5 5 2 5 8

Case 3 remains unchanged after the rain.

Jane plans to open a flower shop in the local flower market. The initial cost includes the booth
license, furnishings and decorations, a truck to transport flowers from the greenhouse to the shop,
and so on. Jane will have to recoup these costs by earning income. She has estimated how much net
income she will earn in each of the following **M** months.

Jane wants to predict how successful her flower shop will be by calculating the
*IRR (Internal Rate of Return)* for the **M**-month period.
Given a series of (time, cash flow) pairs (i, C_{i}), the IRR is the compound interest rate
that would make total cash exactly 0 at the end of the last month. The higher the IRR is, the
more successful the business is. If the IRR is lower than the inflation rate, it would be wise not
to start the business in the first place.

For example, suppose the initial cost is $10,000 and the shop runs for 3 months, with net incomes of
$3,000, $4,000, and $5,000, respectively. Then the IRR **r** is given by:

In this case, there is only one rate (~=8.8963%) that satisfies the equation.

Help Jane to calculate the IRR for her business. It is guaranteed that -1 < **r** < 1, and there
is exactly one solution in each test case.

The first line of the input gives the number of test cases, **T**. **T** test cases follow.
Each test case starts with a positive integer **M**: the number of months that the flower shop
will be open. The next line contains **M** + 1 non-negative integers
**C _{i}** (0 ≤ 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 a floating-point number: the IRR of
Jane's business. `y`

will be considered correct if it is within an absolute
or relative error of 10^{-6} of the correct answer.
See the FAQ for an explanation of what that means,
and what formats of real numbers we accept.

1 ≤ **T** ≤ 100.

Time limit: 30 seconds per test set.

Memory limit: 1GB.

**C _{0}** > 0.

0 ≤

1 ≤ **M** ≤ 2.

1 ≤ **M** ≤ 100.

Sample Input

3 2 200 100 100 3 10000 3000 4000 5000 5 3000 100 100 100 100 100

Sample Output

Case #1: 0.000000000000 Case #2: 0.088963394693 Case #3: -0.401790748826

Sample case #2 and #3 will only appear in large dataset.

Clash Royale is a real time strategy card game. Each card has an attack power and a level. Each player picks 8 cards to form a battle deck; the total attack power of a deck is the sum of the attack power of each of its cards. Players fight with each other by placing cards from their battle decks into the battle arena. The winner of a battle is rewarded with coins, which can be used to upgrade cards. Upgrading a card increases its attack power.

After days of arena fighting, Little Shawn has accumulated a total of **M** coins. He has decided
to upgrade some of his cards. Little Shawn has **N** cards. The i-th card can have any level
from 1 through **K _{i}**; the attack power for the j-th level is

Little Shawn wants to use some or all of his coins to upgrade cards, and then form a deck of exactly 8 cards, so that the deck's total attack power is as large as possible. Can you help him do this? He can upgrade the same card more than once as long as he can afford it, and he does not have to upgrade every card.

The first line of the input gives the number of test cases, **T**. **T** test cases follow.
Each test case starts with 2 integers **M** and **N**, the number of coins and the number of
cards that Little Shawn possesses. Then **N** blocks follow. The i-th block consists of 3
lines describing the i-th card. The first line contains two integers **K _{i}** and

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 maximal possible total attack power of
a deck that Little Shawn can form, using the coins that he has.

Time limit: 60 seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 100.

1 ≤ **K _{i}** ≤ 10.

1 ≤

1 ≤ **M** ≤ 1,000.

**N** = 8.

1 ≤ **A _{i,j}** ≤ 1,000.

1 ≤

1 ≤ **M** ≤ 1,000,000,000.

8 ≤ **N** ≤ 12.

1 ≤ **A _{i,j}** ≤ 1,000,000,000.

1 ≤

Sample Input

2 20 8 3 1 1 10 100 1 2 3 1 1 10 100 1 3 3 1 1 10 100 1 4 3 1 1 10 100 1 5 3 1 1 10 100 1 6 3 1 1 10 100 1 7 3 1 1 10 100 1 8 3 1 1 10 100 1 9 30 10 4 1 1 10 100 200 1 2 3 3 1 1 10 100 2 4 3 1 1 10 100 3 6 4 2 1 10 100 200 4 8 16 3 1 1 10 100 5 10 3 1 1 10 100 6 12 3 1 1 10 100 7 14 3 1 1 10 100 8 16 3 1 1 10 100 9 18 3 1 1 10 100 10 20

Sample Output

Case #1: 422 Case #2: 504

Sample case #2 will only appear in large dataset.

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.

Test Data

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