Ina and the Hyperdimensional War

The otherworld guarded by four goddesses is at war again today, and the prize is followers. Ina, who lost every recent war, decided to win the next one and analysed how the other goddesses behave. She turned every goddess movement into numbers, and she calls each of those a unit move.

A unit move has the following properties.

1. A goddess is a transcendent being, so she crosses between dimensions at will.
2. A goddess likes brevity, so she only moves to integer coordinates.
3. Every goddess movement is measured from the origin.
4. In a unit move $(x_1, x_2, \dots, x_n)$ of $n$ dimensional space, at least one of $x_1, x_2, \dots, x_n$ equals 1. If the first 1 appears at $x_i$, then $x_1, x_2, \dots, x_{i-1}$ are all 0. Among the $n$ unit moves that are given, the position of the first 1 differs from move to move.

Given a coordinate, call it reachable if some combination of unit moves lands exactly on it, and unreachable otherwise. Each unit move may be used any number of times, but the total number of moves cannot exceed 2,000,000,000. That is, the number of times each unit move is used is a non-negative integer, and the sum of those counts is at most 2,000,000,000.

For a reachable coordinate, the number of unit moves used when moving there with as few moves as possible is called the shortest move count. If the given coordinate is the origin, no move is needed and the shortest move count is 0.

For example, suppose the goddesses move in two dimensional space. If the set of unit moves is $\{(1, 0), (0, 1)\}$, then $(2, 1)$ can be written as $(1, 0) + (1, 0) + (0, 1)$, so it is reachable, and no shorter combination exists, so the shortest move count is 3. The coordinate $(-1, 1)$ cannot be reached at all.

Help Ina. Decide whether the other goddesses can reach the given coordinate, and compute the shortest move count when they can.

The first line contains the number of test cases $T$ ($1 \le T \le 100$).

The first line of each test case contains the number of dimensions $n$ ($1 \le n \le 500$). Each of the next $n$ lines describes one unit move: line $i$ contains the $n$ integers $x_{i1}, x_{i2}, \dots, x_{in}$ ($-1000 \le x_{ij} \le 1000$) of unit move $i$, separated by spaces. The unit moves are given in increasing order of the position of their first 1. The line after them contains $n$ integers $y_1, y_2, \dots, y_n$ ($-5 \times 10^8 \le y_i \le 5 \times 10^8$) giving the target coordinate.

The sum of $n$ over all test cases is at most 2000.

Print one line per test case. Print 1 if the other goddesses can reach the given coordinate and 0 if they cannot. When the coordinate is reachable, print the shortest move count on the same line, separated by a space.

A coordinate whose shortest move count exceeds 2,000,000,000 counts as unreachable, so print only 0 for it.