The first line of the input gives the number of test cases, **T**. **T** test cases follow. Each test case consists of **S** which is the side length of the square maze. Then S^{2} numbers follow like a maze to give the numbers that have been assigned to the rooms.

1 2 9 5 3 8 4 6 7

For each test case, output one line containing "Case #x: r d", where x is the test case number (starting from 1), r is the room number of the person who will win and d is the number of rooms he could move. In case there are multiple such people, the person who is in the smallest room will win.

Time limit: 30 seconds per test set.

Memory limit: 1 GB.

1 ≤ **T** ≤ 100.

1 ≤ **S** ≤ 10

1 ≤ **S** ≤ 10^{3}.

Sample Input

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

Sample Output

Case #1: 1 2 Case #2: 6 4

There exist some cities that are built along a straight road. The cities are numbered 1, 2, 3... from left to right.

There are **N** GBuses that operate along this road. For each GBus, we know the range of cities that it serves: the i-th gBus serves the cities with numbers between **A _{i}** and

We are interested in a particular subset of **P** cities. For each of those cities, we need to find out how many GBuses serve that particular city.

The first line of the input gives the number of test cases, **T**. Then, **T** test cases follow; each case is separated from the next by one __blank__ line. (Notice that this is unusual for Kickstart data sets.)

In each test case:

- The first line contains one integer
**N**: the number of GBuses. - The second line contains 2
**N**integers representing the ranges of cities that the buses serve, in the form**A**..._{1}B_{1}A_{2}B_{2}A_{3}B_{3}**A**. That is, the first GBus serves the cities numbered from_{N}B_{N}**A**to_{1}**B**(inclusive), and so on._{1} - The third line contains one integer
**P**: the number of cities we are interested in, as described above. (Note that this is not necessarily the same as the total number of cities in the problem, which is not given.) - Finally, there are
**P**more lines; the i-th of these contains the number**C**of a city we are interested in._{i}

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

, where `x`

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

is a list of **P** integers, in which the i-th integer is the number of GBuses that serve city **C _{i}**.

Time limit: 30 seconds per test set.

Memory limit: 1 GB.

1 ≤ **T** ≤ 10.

1 ≤ **N** ≤ 50

1 ≤ **A _{i}** ≤ 500, for all i.

1 ≤

1 ≤

1 ≤

1 ≤ **N** ≤ 500.

1 ≤ **A _{i}** ≤ 5000, for all i.

1 ≤

1 ≤

1 ≤

Sample Input

2 4 15 25 30 35 45 50 10 20 2 15 25 10 10 15 5 12 40 55 1 10 25 35 45 50 20 28 27 35 15 40 4 5 3 5 10 27

Sample Output

Case #1: 2 1 Case #2: 3 3 4

In Sample Case #1, there are four GBuses. The first serves cities 15 through 25, the second serves cities 30 through 35, the third serves cities 45 through 50, and the fourth serves cities 10 through 20. City 15 is served by the first and fourth buses, so the first number in our answer list is 2. City 25 is served by only the first bus, so the second number in our answer list is 1.

Once upon a day, Mary bought a one-way ticket from somewhere to somewhere with some flight transfers.

For example: SFO->DFW DFW->JFK JFK->MIA MIA->ORD.

Obviously, transfer flights at a city twice or more doesn't make any sense. So Mary will not do that.

Unfortunately, after she received the tickets, she messed up the tickets and she forgot the order of the ticket.

Help Mary rearrange the tickets to make the tickets in correct order.

The first line contains the number of test cases **T**, after which **T** cases follow.

For each case, it starts with an integer **N**. There are **N** flight tickets follow.

Each of the next 2 lines contains the source and destination of a flight ticket.

For each test case, output one line containing "Case #x: itinerary", where **x** is the test case number (starting from 1) and **itinerary** is sorted list of flight tickets which represents the actual itinerary. Each flight segment in the itinerary should be outputted as pair of source-destination airport codes.

Time limit: 30 seconds per test set.

Memory limit: 1 GB.

1 ≤ **T** ≤ 100.

For each case, the input tickets are messed up from an entire itinerary bought by Mary. In other words, it's ensured can be recovered to a valid itinerary.

1 ≤ **N** ≤ 100.

1 ≤ **N** ≤ 10^{4}.

Sample Input

2 1 SFO DFW 4 MIA ORD DFW JFK SFO DFW JFK MIA

Sample Output

Case #1: SFO-DFW Case #2: SFO-DFW DFW-JFK JFK-MIA MIA-ORD

Given an arranged chess board with pieces, figure out the total number of different ways in which any piece can be killed **in one move**. Note: in this problem, the pieces can be killed despite of the color.

For example, if there are 3 pieces King is at B2, Pawn at A1 and Queen at H8 then the total number of pieces that an be killed is 3. H8-Q can kill B2-K, A1-P can kill B2-K, B2-K can kill A1-P

A position on the chess board is represented as A1, A2... A8,B1.. H8

Pieces are represented as

- (K) King can move in 8 direction by one place.
- (Q) Queen can move in 8 direction by any number of places, but can't overtake another piece.
- (R) Rook can only move vertically or horitonzally, but can't overtake another piece.
- (B) Bishop can only move diagonally, but can't overtake another piece.
- (N) Knights can move to a square that is two squares horizontally and one square vertically
**OR**one squares horizontally and two square vertically. - (P) Pawn can only kill by moving diagonally upwards (towards higher number i.e. A -> B, B->C and so on).

The first line of the input gives the number of test cases, **T**. **T** Test cases follow. Each test case consists of the number of pieces , ** N**. **N** lines follow, each line mentions where a piece is present followed by **-** with the piece type

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 the total number of different ways in which any piece can be killed.

Time limit: 30 seconds per test set.

Memory limit: 1 GB.

1 ≤ **T** ≤ 100.

1 ≤ **N** ≤ 10.

Pieces can include K, P

1 ≤ **N** ≤ 64.

Sample Input

2 2 A1-K A8-Q 3 B2-K A1-P H8-Q

Sample Output

Case #1: 1 Case #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.

Test Data

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