Spaceship Defence (Small)

The enemy has boarded your spaceship, and only better tactics will save it. Your soldiers move around the ship with two devices: teleporters and turbolifts.

A teleporter moves a soldier to another room instantly. Every room holds one teleporter, and every room has a color. A soldier standing in a room can use that room's teleporter to move to any other room of the same color at once. The trip takes 0 seconds.

A turbolift moves soldiers between rooms more slowly. It works like an elevator that runs in many directions. One turbolift carries soldiers from one fixed room to one other fixed room, and the trip takes a fixed amount of time. Turbolifts have two properties.

• A turbolift runs one way. If a turbolift carries soldiers from room $a$ to room $b$, that same turbolift cannot carry them from room $b$ to room $a$. A separate turbolift may run in that direction.
• Several soldiers can use the same turbolift, and they do not interfere with each other.

You are given the location and the destination of several soldiers. For each soldier, find the smallest amount of time the trip from the location to the destination can take.

The first line contains the number of test cases $T$. $T$ test cases follow.

The first line of each test case contains the number of rooms in the spaceship, $N$. The rooms are numbered from 1 to $N$. The next $N$ lines each contain one string, giving the color of room 1 through room $N$ in order. Each string uses only the lowercase English letters a to z and the digits 0 to 9, and its length is at most 2.

The next line contains the number of turbolifts, $M$. The next $M$ lines each contain three space separated integers $a_i$, $b_i$, $t_i$, meaning that a turbolift carries soldiers from room $a_i$ to room $b_i$ in $t_i$ seconds.

The next line contains the number of soldiers under your command, $S$. The next $S$ lines each contain the location $p_j$ and the destination $q_j$ of one soldier, separated by a space.

The limits are as follows.

• $1 \le T \le 10$
• $1 \le N \le 1000$
• $0 \le M \le 3000$
• $1 \le a_i, b_i \le N$
• $0 \le t_i \le 1000$
• $1 \le S \le 100$
• $1 \le p_j, q_j \le N$

For each test case, first print one line of the form Case #x:, where x is the test case number starting from 1. Then print $S$ lines, one integer on each. On line $j$, print the smallest number of seconds a soldier needs to travel from room $p_j$ to room $q_j$. If there is no path from room $p_j$ to room $q_j$, print -1.