A modern building can be viewed as a 3D array of grids of m rows (numbered 0 to m-1), n columns (numbered 0 to n-1)and h floors (numbered 0 to h-1). From a grid you can take any of the 4-neighbouring grids at a unit time (or you walk at a speed of 1 block per unit time). You can only go up and down to access other floors using either of the staircases. Using the staircase you can go up at the rate of 1 floor in 2 units of time, and down at the rate of 1 floor in 1 units of time. In other words going 1 floor up takes 2 units of time and going down 1 floor takes 1 unit of time. You may use stairs to navigate within the same floor as a non-obstacle grid as well. Passing through stairs in the same floor as if they were non-obstacle regions is acceptable. Calculate the time required to reach a goal from a specific source.

Constraints: 0<m,n≤300, 0<h≤50

Input format

The first input is T, the number of test cases. For every test case, the first line is m (number of rows), n (number of columns) and h (number of floors). Thereafter details of all floors are given from index 0 (ground floor) to index h-1 (top floor). Each floor details has m rows of n columns each. A cell can be 0 (obstacle), 1 (free) or 2 (staircase). The staircases shall run through all the floors. The next line contains q, the number of queries. Each query is a source-goal pair for the same map. For every query, the next line contains the floor number, row number and column number of source and the next line contains the floor number, row number and column number of goal.

Output format

For every test case, 1 line printing the time to reach the goal. Print -1 if the source and goal are disconnected.

Sample Input

1 (number of test cases)

5 5 3 (m, n, h: double check the order of variables)

<ground 0^th floor details follow>

1 1 1 1 2

1 1 1 1 1

1 1 0 0 0

1 1 0 1 2

1 1 0 1 1

<1^st floor details follow>

1 1 1 1 2

1 1 1 1 1

0 0 0 0 0

1 1 1 1 2

1 1 1 1 1

<2^nd floor details follow>

1 1 0 1 2

1 1 1 1 1

1 0 0 0 0

1 1 1 1 2

1 1 1 1 1

1 (no. of queries)

0 0 0 (source for query 1, floor, row, column, double check the order of variables)

0 4 4 (goal for query 1, floor, row, column, double check the order of variables)

Sample Output

22

Explanation:

Legend: Gray (obstacle), White (free), Blue (Stairs), Green (Path), S (source), G (goal), Numbered (cost till step)