## Shipping

The My-way-or-the-Highway Trucking company has filed for
bankruptcy. As part of the settlement, all of the company's
trucks are being purchased by a rival company (Wheels of Fortune).
Wheels of Fortune is eager to get their new trucks on the road,
but they need to get all of them from their old home base
to the new Wheels-of-Fortune headquarters. The limiting factor
in this truck-moving task is the capacity of the roads around the
headquarters.

You have been contracted to help Wheels of Fortune with this
problem. In the course of its business, the company
has developed accurate estimates
of how many trucks will be able to traverse various roads at
different hours of the day. With that information they would like
you to calculate the number of trucks that they can expect to arrive
at the shipping centers for each of those hours.

#### Input

The input for this problem consists of (1) a line containing the number (an
integer)
of hours `H`
for which the road capacities are modeled. For each hour, there
follows, on a single line, the number of available interchanges (`N`)
-- spots
at which the trucks can
switch from one road to another. Following that line are `N`
lines of `N` whitespace-separated integers.
(`N` will be no larger than 100.)
The `j`th integer on the `i`th
such line will indicate the maximum number of trucks that will be
able to make it from the `i`th to the `j`th interchange
at that particular hour of the day. Thus, the input is the matrix of
road capacities.

If there is no road connecting
the two interchanges (or if `i == j`), the capacity will be 0.
You may assume that the first line (`i = 1`) will represent the
trucks' origin and that the last line (`i = N`) represents
the goal, the shipping center.
This pattern of inputs repeats `H` times, one for each modeled
hour. (Note that the number of interchanges may change from hour
to hour as roads open or close.)

#### Output

There should be one output line for each modeled hour -- it should
contain only the largest number of trucks that traffic conditions
will permit to reach the shipping center from their starting
point in that hour.

#### Example Input

2
4
0 10000 10000 0
0 0 1 10000
0 1 0 10000
0 0 0 0
6
0 16 13 0 0 0
0 0 10 12 0 0
0 4 0 0 14 0
0 0 9 0 0 20
0 0 0 7 0 4
0 0 0 0 0 0

#### Example Output

20000
23