Aqualoo Plants

All submissions for this problem are available.

A rectangular garden is divided into square shaped cells where each cell consists of a plant. Some plants depending upon their nature need more water than others and some may not require water at all. Invisible water taps keep teleporting around the garden. Each water tap gives water to a plant for a constant time and then teleports to another( or reappears in the same cell ) to give water to another plant( or the same plant ). To simplify the structure, each water tap moves with respect to a base cell, Row offset set and a Column offset set and keeps repeating through the set. For example:

Consider a 6 X 6 size rectangle:

Therefore,

Total Rows = 6
Total Columns = 6
Total cells = Total plants = 36

Now consider a tap with following properties

1. Base cell: 0
2. Row Offset Set: 0 1 2 0 0
3. Column Offset Set: 1 0 0 1 2

The cell numbers for the garden in this case will be:

0 1 2 3 4 5
6 7 8 9 10 11
12 13 14 15 16 17
18 19 20 21 22 23
24 25 26 27 28 29
30 31 32 33 34 35

This means the tap starts with giving water to cell '1'( Row offset 0, column offset 1 with respect to cell '0' i.e. the base cell ) and then moves to cells 6 -> 12 -> 1 -> 2. The new cell position is with respect to the base cell, the current row and column offset and has got nothing to do with the previous cell positions where water tap was teleported. Also note that the tap would continuously move in the following order 1->6->12->1->2->1->6->12... and so on.

All the water taps are synchronised i.e. all of them change the cells at the same time, give water for the same amount of time and so on. Consequently, there may be such plants, which at some time instant get water from every tap in the garden. These plants are called Aqualoo plants.

Now given the taps and their respective base cell, row offset set and column offset set, you have to give out the total Aqualoo plants in the garden.

Notes
- Remember that for the plant to be Aqualoo, every tap in the garden should water this plant at same time instant.
- Every tap may or may not have a different base cell, row offset and column offset.

Input

1. Number of test cases = 'T' ( 1 <= T <= 300 )
2. For each test case, first line of input contains number of rows = 'R', followed by number of columns = 'C' and total number of water taps = 'N' ( 1 <= R <= 50, 1 <= C <= 50, 1 <= N <= 6 ).
3. For each tap, first line of input contains base cell number = 'B', followed by length of the row offset set and column offset set = 'L' ( 0 <= B < R * C, 1 <= L <= 25 ).
4. Next line contains row offset set, where each value lies in range ( -R, +R )( not inclusive ).
5. Next line contains column offset set, where each value lies in range ( -C, +C )( not inclusive ).

Output

1. Each line of output contains total Aqualoo plants

Example

Input:
2

6 6 2
7 1
2
3
35 1
-2
-1

6 6 2
13 4
0 1 1 0
0 1 2 3
4 3
0 1 2
0 0 0

Output:
1
1