You are given a cost matrix of dimensions m X n. The problem of finding the minimal path from top-left corner to some cell in the matrix is well studied. Here, we are gonna add a little twist.

To refresh your memory, the total cost of a path is sum total of cost of all cells visited in the path. 

Only 2 moves are allowed: either to go down by a row, or move right by a column. You cannot leave the matrix at any time.

Also, some of the cells are marked as obstacles and cannot be stepped upon.

Several queries of the form: tx ty k are to be answered. The output for this query should be kth minimum cost of a path from top-left corner to cell indexed at ty column in tx row.

Input:

The first line contains the number of test cases T, 

The first line of each test case contains two space-separated integers m and n.

The next m lines each contain n integers, denoting the matrix.

The next line contains an integer q, denoting the number of queries to come.

The next q lines each contain 3 space separated integers, tx ty and k

Output:

For each query output the kth shortest path

Constraints:
1 ≤ T ≤ 5
1 ≤ m,n ≤ 100
0 ≤ tx < m
0 ≤ ty <n
1 ≤ k ≤ 101
1 ≤ q ≤ 1000
Notes:
The obstacles in matrix are marked by "##" (quotes only for clarity)
The values in every cell that is not an obstacle, varies from -9 to 99 only.
tx and ty are both 0-indexed.
If k exceeds the total paths to cell (tx, ty) output "Not so many paths"
If (tx, ty) is an obstacle, output "Obstacle".
There will never be an obstacle on the top-left corner or bottom-right corner.

SAMPLE INPUT
2
2 2
1 2
3 4
2
1 1 1
1 1 2
2 2
1 2
## 4
3
1 1 1
1 1 2
1 0 1

SAMPLE OUTPUT
7
8
7
Not so many paths
Obstacle
from collections import deque
 
for _ in xrange(input()):
    R, C = map(int, raw_input().split())
    li = []
    
    for _ in xrange(R):
        li.append(raw_input().split())
     
    res = []
    for i in xrange(R):
        t = []
        for j in xrange(C):
            t.append([])
        res.append(t)
    res[0][0].append(li[0][0])
    start = int(li[0][0])
    for c in xrange(1, C):
        if start is not None and li[0][c] != "##":
            start += int(li[0][c])
            res[0][c].append(start)
        else:
            start = None
          
    start = int(li[0][0])        
    for r in xrange(1, R):
        if start is not None and li[r][0] != "##":
            start += int(li[r][0])
            res[r][0].append(start)
        else:
            start = None     
    for r in xrange(1, R):
        for c in xrange(1, C):
            top = res[r - 1][c]
            left = res[r][c - 1] 
            p1 = 0
            p2 = 0
            
            if li[r][c] == "##":
                continue
            
            data = int(li[r][c])
            
            while p1 < len(top) and p2 < len(left) and p1 + p2 < 101:
                if top[p1] < left[p2]:
                    res[r][c].append(top[p1] + data)
                    p1 += 1
                else:
                    res[r][c].append(left[p2] + data)
                    p2 += 1
            
            while p1 < len(top) and p1 + p2 < 101:
                res[r][c].append(top[p1] + data)
                p1 += 1
                
            while p2 < len(left) and p1 + p2 < 101:
                res[r][c].append(left[p2] + data)
                p2 += 1
                
    
    
    Q = input()
    
    for _ in xrange(Q):
        s, t, k = map(int, raw_input().split())
        if li[s][t] == "##":
            print "Obstacle"
        elif k > len(res[s][t]):
            print "Not so many paths"
        else:
            print res[s][t][k - 1]