Fast Fingers Thomas is delivering poutine to Wilson's restaurants!

Fast Fingers Thomas will drive a truck on a directed, weighted graph with $N$ vertices. The weight of each edge in the graph is the length of the edge. He has $Q$ trips he needs to make.

Each trip has three parameters, a source vertex $s_i$, a destination vertex $t_i$, and a number of days $d_i$. Thomas has $d_i$ days to travel from vertex $s_i$ to vertex $t_i$. In a given day, Thomas starts at a vertex and traverses a nonnegative number of edges, ending the day at some vertex (possibly the same one). Define $f(s_i,t_i,d_i)$ to be the smallest value such that, in a single day, the sum of the weights of the edges that Thomas drives on does not exceed $f(s_i,t_i,d_i)$, and subject to this, Thomas can get from $s_i$ to $t_i$ in $d_i$ days. In the event that it's impossible to do this, Thomas does no driving and $f(s_i,t_i,d_i)$ is zero.

Constraints

$2\le N\le 100$

$1\le Q\le {10}^5$

$0\le w_{ij}\le {10}^9$

$1\le s_i,t_i\le N$

$s_i\ne t_i$

$1\le d_i<N$

All queries are pairwise distinct.

Input Specification

The first line contains a single positive integer, $N$.

The next $N$ lines contain $N$ space-separated non-negative integers. The $j$th integer in the $i$th line of this section, $w_{ij}$, indicates the length of the directed edge connecting vertex $i$ to vertex $j$, or $0$ if no such edge exists. It is guaranteed there are no self-loops.

The next line contains a single positive integer, $Q$.

The next $Q$ lines each contain three space-separated positive integers, $s_i$, $t_i$, and $d_i$, representing a query for $f(s_i,t_i,d_i)$.

Output Specification

Output $Q$ lines. On the $i$th line, output the answer to the $i$th query.

Sample Input

3
0 1 2
1 0 1
2 1 0
2
1 3 1
1 3 2

Sample Output

2
1