Supercap Travels

In 2037, two and a quarter centuries after the first commercial railway locomotive, supersonic magnetic levitation capsules called supercaps entered service. A supercap runs at up to $512$ m/s, so a trip between two cities takes seconds instead of hours.

A supercap changes speed instantly, and every speed it holds is a power of two in m/s. One trip covers exactly $D$ meters, starts at rest, ends at rest, and has four parts.

1. Acceleration. The capsule runs one second at $2^0 = 1$ m/s, one second at $2^1 = 2$ m/s, one second at $2^2 = 4$ m/s, and so on, doubling every second until it reaches its upper speed $U$. Every speed on the way, $U$ included, is held for exactly one second.
2. Upper glide. The capsule holds $U$ for $g$ further seconds, where $g \ge 0$.
3. Deceleration. The capsule halves its speed every second, from $U/2$ down to the fixed lower speed of $16$ m/s. Every speed on the way, $16$ m/s included, is held for exactly one second.
4. Final glide. The capsule holds $16$ m/s for a whole number of seconds, then $8$ m/s, then $4$ m/s, then $2$ m/s, then $1$ m/s, and then it stops. Each of these five counts may be zero, so a speed may be skipped.

The speed against time graph below shows a typical trip.

The upper speed is not a free choice. The capsule accelerates as far as it can, so $U$ is the largest power of two, at most $512$, whose acceleration and deceleration parts alone already fit inside the trip: $(2U - 1) + (U - 16) \le D$.

The fare of a trip is proportional to

$A - 100B$

where $A$ is the number of seconds spent above $16$ m/s and $B$ is the number of seconds spent at $16$ m/s or below. Time above the lower speed earns money, and one second at or below the lower speed costs the corporation 100 times what one second above it earns. Every city is priced by its best trip, so the fare score of a city at distance $D$ is the largest value of $A - 100B$ over all trips that cover exactly $D$ meters.

In the first build phase the capital city $Z$ of a region gets one link into each neighbouring region, and that link reaches exactly one city of that region. Cities inside the same region are never linked to each other. For every neighbouring region, report the city with the largest fare score.

The first line contains an integer $T$ ($1 \le T \le 10$), the number of test cases.

Each test case begins with a line holding an integer $R$ ($1 \le R \le 10$), the number of neighbouring regions. The descriptions of the $R$ regions follow in order.

Each region description begins with a line holding an integer $C$ ($1 \le C \le 10$), the number of cities of that region that have a supercap station. Each of the next $C$ lines holds a city name $Y$ and an integer $D$ ($1000 \le D \le 2 \times 10^6$). The name $Y$ is one word of English letters, and $D$ is the distance in meters from the station in the capital city $Z$ to the station in city $Y$. Inside one region all distances are distinct.

Print one line for each test case. The line starts with Case #x:, where $x$ is the number of the test case counting from $1$, then one space, then the names of the chosen cities separated by single spaces. The names come in the same order as the regions of that test case. If several cities of one region reach the same largest fare score, choose the one that appears first in the input.