Context

One day like today, 83 years ago --i.e., on May 11th, 1930-- Edsger Dijkstra was born in Netherlands. He was one of the greatest computer scientists in History, and designed a famous algorithm that bears his name. Dijkstra's algorithm is able to compute the shortest path in a graph, in a very efficient way.

However, what Dijkstra did not take into account is that fuel does not last forever, and you need to go to a gas station from time to time.

The Problem

We have bought a new eco-car which has a fuel tank of only 8 litres. However, it has an autonomy of only 100 km, so you can not drive for more than 100 km without stoping at a gas station.

We have a map with some locations and roads between them; some of these locations are gas stations. You have to compute the shortest path between to given locations, with the restriction that you can not drive for more than 100 km without passing throw a gas station.

The Input

The input begins with an integer, indicating the number of test cases.

For each test case, the first line contains three integer numbers, N, R and Q, indicating the number of locations, the number of roads, and the number of queries we want to do, respectively. N is not bigger than 250.

Then, there are N lines, one for each location. Each line contains a letter "G" if the corresponding location is a gas station, and "O" otherwise.

Then, there are R lines, one for each road. Each line contains three integers, V, W and C, indicating that there is a road from V to W whose length is C km. The road from V to W is the same as the road from W to V. Locations are numbered starting from 1.

Finally, there are Q lines, one for each query. Each query consists of two integers, A and B, the start and end locations to compute the shortest gas path.

The Output

Sample Input

1
4 4 3
O
O
G
O
1 2 51
2 4 50
1 3 80
3 4 100
1 4
4 3
3 2

Sample Output

CASE 1
180
100
NO GAS PATH

OMP'13
Facultad de Informatica
Universidad de Murcia (SPAIN)