Shipping Routes

Problem

A shipping company needs a program that can quickly quote costs to prospective customers. The cost of a shipment depends on the size of the shipment and on how many shipping legs it requires. A shipping leg connects two distinct warehouses. Because not every pair of warehouses is directly connected by a leg, sending a shipment from one warehouse to another may require more than one leg.

A data set describes from 1 to 30 warehouses. Each warehouse is identified by a two-letter code made of capital letters only. A shipping leg can exist between any two distinct warehouses, and every leg is bidirectional.

The cost of a shipment equals (the size of the shipment) × (the number of shipping legs required) × $100.

Given the warehouses and the existing shipping legs, together with a request consisting of a shipment size, a source warehouse, and a destination warehouse, output the cheapest possible cost, sending the shipment along the fewest legs. If no route connects the source to the destination, report that the request cannot be fulfilled.

Input

The first line contains an integer $T$ ($1 \le T \le 10$), the number of data sets. Each data set describes a separate shipping configuration.

Each data set begins with a line containing three integers $M$, $N$, and $P$:

$M$ ($1 \le M \le 30$): the number of warehouses.
$N$ ($0 \le N \le M(M-1)/2$): the number of shipping legs.
$P$ ($0 \le P \le 10$): the number of shipping requests.

The next line contains the $M$ two-letter warehouse codes (capital letters only), separated by single spaces.

The following $N$ lines each describe a shipping leg as two distinct warehouse codes XX YY, meaning there is a direct bidirectional leg between XX and YY.

The final $P$ lines are the shipping requests, one per line. Each request is an integer shipment size $S$ ($1 \le S \le 20$) followed by two distinct warehouse codes AA BB, the source and destination of the shipment.

The input is valid and consistent: each shipping leg appears at most once per data set, and every code refers to a warehouse in the current data set.

Output

For each data set, in order:

Print a line reading DATA SET k, where k is the data set number starting from 1.
Print a blank line.
Print $P$ result lines. For each request, print the cheapest cost as $A (a dollar sign immediately followed by the integer amount $A$, for example $500), or the exact phrase NO SHIPMENT POSSIBLE if no route connects the source to the destination.

Separate consecutive data sets with a single blank line.