차원 워프 드라이브

3133년, 우주 여행은 매우 흔한 일이 되었다. 차원 워프 드라이브를 이용하면 멀리 떨어진 두 행성 사이를 거의 즉시 이동할 수 있다.

차원 워프 드라이브는 상대 굴곡 양자화 우주(Relativistic Curved Quantized Space, RCQS) 이론을 따른다. 이 이론에 따르면 우주는 11개의 차원으로 이루어져 있으며, 각 차원은 자기 자신으로 휘어져 있다. 즉, 한 방향으로 계속 나아가면 결국 출발한 지점으로 되돌아온다.

또한 우주는 양자화되어 있어 각 차원에서 가능한 위치는 0부터 10까지 총 11개뿐이다. 위치 11은 위치 0과 같으므로, 모든 좌표는 11로 나눈 나머지로 생각한다.

3075년에 첫 번째 워프 궤도가 발견되었다. 워프 궤도는 11개의 정수로 이루어진 좌표를 가진다. 어떤 워프 궤도를 한 번 사용하면 우주선은 현재 위치의 각 차원 좌표에 그 궤도의 좌표를 더한 곳(각 차원마다 11로 나눈 나머지)으로 이동한다. 한 번 발견된 워프 궤도는 발견된 해부터 몇 번이든 다시 사용할 수 있다.

현재 위치와 목표 위치가 주어질 때, 그때까지 발견된 워프 궤도만 사용하여 목표 위치에 도달할 수 있는 가장 이른 연도를 구하는 프로그램을 작성하시오. 어떤 연도가 되어도 도달할 수 없다면 unreachable을 출력한다.

예를 들어 현재 위치가 $(0,0,0,0,0,0,0,0,0,0,0)$이고 목표 위치가 $(0,0,3,0,0,3,0,0,3,0,0)$이라고 하자. 3075년에 궤도 $(0,0,1,0,0,1,0,0,1,0,0)$이, 3082년에 궤도 $(0,0,1,0,0,2,0,1,0,0,0)$이 발견되었다면, 3075년에 발견된 궤도를 세 번 사용하여 목표 위치에 바로 도달할 수 있다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 다음과 같이 구성된다.

• 첫째 줄에 워프 궤도의 개수 $n$이 주어진다. ($n < 1000$)
• 둘째 줄에 여행을 시작하는 현재 위치가 주어진다. 우주는 11차원이므로 좌표는 11개의 정수로 이루어지며, 각 값은 0 이상 10 이하이다.
• 셋째 줄에 도달하려는 목표 위치가 주어진다. 각 값은 0 이상 10 이하이며, 이 위치는 시작 위치와 항상 다르다.
• 이어지는 $n$개의 줄에는 각각 12개의 정수가 주어진다. 처음 11개는 워프 궤도의 좌표이고, 마지막 정수는 그 궤도가 발견된 연도이다. 연도는 3075 이상 100000 이하이다.

각 테스트 케이스마다 워프 궤도를 사용하여 목표 위치에 도달할 수 있는 가장 이른 연도를 한 줄에 출력한다. 어떤 연도가 되어도 도달할 수 없다면 unreachable을 출력한다.