Spaceship Defence (Large)

The enemy has boarded your spaceship. Your soldiers move around the ship with two devices, teleporters and turbolifts.

Every room holds one teleporter, and every room has one color. A soldier standing in a room uses that room's teleporter to move instantly to any other room of the same color. This move costs no time.

A turbolift carries soldiers from one room to one other room, and the trip takes a fixed amount of time. A turbolift runs in one direction only. A turbolift that carries soldiers from room $a$ to room $b$ cannot carry them from room $b$ to room $a$, though a separate turbolift may do that. Several soldiers can use the same turbolift at once, and they do not interfere with each other.

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

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

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

The next line contains an integer $M$, the number of turbolifts. Each of the next $M$ lines contains 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 an integer $S$, the number of soldiers. Each of the next $S$ lines contains two integers $p_j$ and $q_j$, the starting room and the destination room of one soldier.

Constraints

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

For each test case, first print one line holding Case #x:, where $x$ is the test case number starting from 1. Then print $S$ lines. Line $j$ holds the smallest number of seconds a soldier needs to travel from room $p_j$ to room $q_j$, as an integer. If no such trip exists, print -1.