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