초차원전쟁 이나

네 여신이 지키는 이(異)세계에서는 오늘도 신도를 모으려는 전쟁이 벌어진다. 최근 전쟁에서 계속 지기만 한 여신 이나는 다음 전쟁만큼은 이기겠다고 다짐하고 다른 여신들의 행동 패턴을 분석했다. 이나는 여신들의 이동을 전부 수치로 옮기는 데 성공했고, 이를 단위 이동이라 부르기로 했다.

단위 이동의 성질은 다음과 같다.

1. 여신은 초월적인 존재라서 차원을 마음대로 넘나든다.
2. 여신은 간결함을 좋아해서 정수 좌표로만 이동한다.
3. 여신의 이동은 원점을 기준으로 한다.
4. $n$차원 공간의 단위 이동 $(x_1, x_2, \dots, x_n)$에서 $x_1, x_2, \dots, x_n$ 중 적어도 하나는 1이다. 처음 1이 나오는 위치가 $x_i$라면 $x_1, x_2, \dots, x_{i-1}$은 모두 0이다. 주어지는 $n$개의 단위 이동은 처음 1이 나오는 위치가 서로 다르다.

어떤 좌표가 주어졌을 때 단위 이동을 적당한 순서로 조합해 그 좌표에 닿을 수 있으면 이동 가능한 위치, 닿을 수 없으면 불가능한 위치라고 한다. 각 단위 이동은 몇 번이든 사용할 수 있지만 전체 이동 횟수는 20억(2,000,000,000)번을 넘길 수 없다. 즉 각 단위 이동을 사용한 횟수는 음이 아닌 정수이고, 그 합이 20억 이하여야 한다.

도달 가능한 위치라면 가장 적은 수의 단위 이동으로 갔을 때 사용한 단위 이동의 개수를 최단 이동 횟수라고 한다. 주어진 좌표가 원점이면 한 번도 움직이지 않아도 되므로 최단 이동 횟수는 0이다.

예를 들어 여신이 2차원 공간에서 움직인다고 하자. 단위 이동의 집합이 $\{(1, 0), (0, 1)\}$이면 $(2, 1)$은 $(1, 0) + (1, 0) + (0, 1)$로 표현되므로 이동 가능한 위치이고, 이보다 적은 횟수로는 갈 수 없으므로 최단 이동 횟수는 3이다. 반면 $(-1, 1)$로는 갈 수 없다.

이나를 도와 주어진 좌표에 다른 여신들이 도달할 수 있는지 판정하고, 도달할 수 있다면 최단 이동 횟수를 구하자.

첫 줄에 테스트 케이스의 수 $T$($1 \le T \le 100$)가 주어진다.

각 테스트 케이스의 첫 줄에는 차원의 수 $n$($1 \le n \le 500$)이 주어진다. 이어지는 $n$개의 줄 중 $i$번째 줄에는 $i$번 단위 이동을 이루는 $n$개의 정수 $x_{i1}, x_{i2}, \dots, x_{in}$($-1000 \le x_{ij} \le 1000$)이 공백을 사이에 두고 주어진다. 단위 이동은 처음 1이 나오는 위치가 커지는 순서로 주어진다. 그다음 줄에는 목표 좌표를 나타내는 $n$개의 정수 $y_1, y_2, \dots, y_n$($-5 \times 10^8 \le y_i \le 5 \times 10^8$)이 주어진다.

모든 테스트 케이스의 $n$을 더한 값은 2000을 넘지 않는다.

각 테스트 케이스마다 한 줄씩 출력한다. 다른 여신들이 주어진 좌표에 도달할 수 있으면 1을, 도달할 수 없으면 0을 출력한다. 도달할 수 있으면 같은 줄에 최단 이동 횟수를 공백으로 구분해 이어서 출력한다.

최단 이동 횟수가 20억을 넘는 좌표는 도달할 수 없는 좌표로 보고 0만 출력한다.