Gio was given the graph in the figure below by his teacher. Given the starting vertex 1 and an ending vertex 4, he was asked to count the number of paths of length 3 from 1 to 4.

Gio answered that there are 4 paths:

1->2->1->4, 
1->2->3->4, 
1->4->3->4, and 
1->4->5->4.

Gio was asked again to count the number of paths of length 3 from 4 to 3. He easily counted 3 paths:

4->3->4->3, 
4->5->4->3, and 
4->2->5->3

Now Gio's exercise can easily be solved using a computer.

INPUT

The input data consists of several directed graphs and test cases for each graph. The first line in the input file is an integer $1 \le n \le 50$ referring to the number of graphs. Each graph description is introduced by a line containing the letter "G". The next line contains two integers: the number of vertices $1 \le v \le 100$ and the number of directed edges, or arcs $1 \le a \lt 9900$. This is followed by a lines. Each of these lines refer to an edge and consists of 2 integer, the source vertex s of the edge and the sink vertex e.

The test cases for the graph is introduced by a line containing the character "T". The next line contains an integer t referring to the number of test cases. Each test case is in a line containing 3 integers: x, y, and l.

x is the starting vertex in the path, y is the ending vertex in the path, and l is the length of the path from vertex x to vertex y.

OUTPUT

For each test case, print the number of paths of length l from vertex x to vertex y.

SAMPLE INPUT

2
G
5 10
1 2
1 3
1 4
2 1
2 3
3 4
4 3
4 5
5 2
5 4
T
5
1 4 3
4 3 3
1 1 4
2 5 5
2 4 1
G
4 8
1 2
1 4
2 1
2 3
3 2
3 4
4 1
4 3
T
2
2 4 2
1 1 4

SAMPLE OUTPUT

4
3
2
6
0
2
8