11579번 - 초차원전쟁 이나 출처

4명의 여신에 의해 수호되고 있는 이(異)세계는 오늘도 여전히 신도들을 모으기 위한 전쟁이 일어나고 있다. 최근 전쟁에서 계속 패하기만 했던 여신 이나는 다음 전쟁에서는 꼭 이기리라 다짐하고 다른 여신들의 행동 패턴을 분석하였다. 결국 이나는 모든 여신들의 이동을 수치화하는데 성공했으며 이를 단위 이동이라 부르기로 했다.

단위 이동의 몇 가지 특징을 정리해보면 다음과 같다.

1. 여신들은 투명하진 않지만 초월적인 존재이기 때문에 차원을 마음대로 넘나들 수 있다.
2. 여신들은 간결함을 좋아하기 때문에 정수 좌표로만 이동한다.
3. 여신들의 이동은 원점을 기준으로 한다.
4. n차원 공간의 단위 이동 (x₁, x₂, ..., x_n)이 있다고 하자. 여신들은 게으르기 때문에 x₁, x₂, ..., x_n 중 적어도 한 가지 값은 1임이 보장된다. 또한, 단위 이동 (x₁, x₂, ..., x_n)에서 처음 나오는 1의 위치가 x_i라면 x₁, x₂, ..., x_i-1은 0이 보장된다. 처음 나오는 1의 위치는 모두 다르다.

어떤 좌표가 주어졌을 때 단위 이동을 적당한 순서로 조합하여 도달할 수 있으면 이동 가능한 위치, 없으면 불가능한 위치라고 한다. 이때, 각 단위 이동은 몇 번이고 사용할 수 있다. 단, 최대 20억 번만 움직일 수 있다.

만약 도달 가능한 위치의 경우, 가장 적은 수의 단위 이동을 사용해 이동했을 때 사용된 단위 이동의 수를 최단 이동 횟수라고 한다. 즉, 어떤 위치로의 이동 횟수 x가 같은 위치로 움직이는 다른 모든 이동 횟수 y에 대해 x ≤ y를 만족 한다면 x는 최단 이동 횟수이다.

예를 들어 여신들이 2차원 공간에서 움직인다고 가정하자. 만약 단위 이동의 집합이 {(1, 0), (0, 1)}이라면 (2, 1)은 (1, 0)+(1, 0)+(0, 1)과 같이 표현할 수 있으므로 이동 가능한 위치이고 다른 어떤 이동보다 이보다 적은 횟수로 움직일 수 있지 않으므로 최단 이동 횟수는 3이다. 반면에 (-1, 1)로는 이동할 수 없다. 즉 단위 이동의 횟수는 항상 음이 아닌 정수여야 한다.

이나는 특정 위치가 주어졌을 때 다른 여신들이 그 위치로 움직일 수 있는지 없는지를 빠르게 판단하고, 그 위치까지 가는데 필요한 최단 이동 횟수를 계산하는 알고리즘을 설계하여 다음 전쟁 때 사용하려 한다. 하지만 할 일이 많기에 신실한 신도인 당신에게 이 일을 맡기기로 했다.

여신 이나를 도와 전쟁에서 승리하기 위한 알고리즘을 설계하자.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 차원의 수를 나타내는 양의 정수 n(1 ≤ n ≤ 500)이 주어진다. 다음 줄부터 여신들의 단위 이동들이 n개의 줄에 걸쳐 주어진다. i번째 줄에는 i번 단위 이동을 나타내는 n개의 정수 x_ij(1 ≤ i ≤ n, 1 ≤ j ≤ n, -1,000 ≤ x_ij ≤ 1,000)가 빈칸을 사이에 두고 주어진다. 단위 이동은 처음 나오는 1의 위치가 증가하는 순서대로 주어진다. 그 다음 줄에는 특정 위치의 좌표를 나타내는 n개의 정수 y_i(1 ≤ i ≤ n, -5×10⁸ ≤ y_i ≤ 5×10⁸)가 주어진다.

각 테스트 케이스별로 한 줄에 한 개씩 다른 여신들이 주어진 특정 좌표에 도달할 수 있다면 1, 없다면 0을 출력한다. 만약 도달할 수 있다면, 같은 줄에 추가로 최단 이동 횟수를 빈칸으로 구분하여 출력한다.