토너먼트 조작

축구 토너먼트에 $n$개의 팀이 참가한다. 첫 번째 라운드에서는 $n/2$번의 경기가 열리고, 각 경기에서 이긴 팀이 다음 라운드로 진출한다. 두 번째 라운드에서는 $n/4$번의 경기가 열리며, 이런 방식으로 라운드를 거듭하다가 마지막 결승전에서 두 팀이 맞붙는다. 결승전에서 이긴 팀이 토너먼트의 우승팀이 된다.

선영이는 어느 축구팀의 구단주이다. 세계에서 가장 강한 팀은 아니지만 꽤 강한 팀이어서, 대회에 참가한 팀 가운데 적어도 절반은 확실히 이길 수 있다. 또한 선영이네 팀이 이기지 못하는 모든 팀 $t$에 대해, 팀 $t$를 이기면서 동시에 선영이네 팀에게는 지는 팀 $t'$가 항상 존재한다.

당신은 대진표를 마음대로 짤 수 있다. 즉, 각 라운드에서 그 라운드에 진출한 팀들을 원하는 대로 둘씩 짝지어 경기를 배정할 수 있다. 경기의 승패 자체는 두 팀의 상대 전적으로 이미 정해져 있어 바꿀 수 없지만, 누가 누구와 붙을지는 당신이 정한다. 선영이네 팀(1번 팀)이 우승하도록 대진표를 짜는 프로그램을 작성하시오.

우승이 가능한 대진표가 여러 개라면, 그중 사전순으로 가장 작은 하나만 출력한다. 사전순의 정의는 아래 '출력'에서 설명한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 테스트 케이스의 개수는 $20$개 이하이다.

각 테스트 케이스의 첫째 줄에는 대회에 참가하는 팀의 수 $n$이 주어진다($2 \le n \le 8$이며, $n$은 $2$의 거듭제곱이다). 팀은 $1$번부터 $n$번까지 번호가 매겨져 있으며, 선영이네 팀의 번호는 $1$번이다.

이어지는 $n$개의 줄에는 각각 길이가 $n$인 이진 문자열이 주어진다. $j$번째 줄의 $k$번째 문자가 1이면 팀 $j$가 팀 $k$를 이길 수 있다는 뜻이고, 0이면 그렇지 않다는 뜻이다(토너먼트 경기이므로 무승부는 없다). 팀은 자기 자신과 경기할 수 없으므로 $j$번째 줄의 $j$번째 문자는 항상 0이다. 서로 다른 $j$와 $k$에 대해, $j$번째 줄의 $k$번째 문자와 $k$번째 줄의 $j$번째 문자는 서로 다르다.

입력은 파일의 끝까지 계속된다.

각 테스트 케이스에 대해, 선영이네 팀이 우승하는 대진표를 $n-1$개의 줄로 출력한다.

처음 $n/2$개의 줄은 첫 번째 라운드의 경기들이고, 그다음 $n/4$개의 줄은 두 번째 라운드의 경기들이며, 그렇게 이어지다가 마지막 한 줄이 결승전이다. 어떤 라운드의 경기들에 등장하는 팀은 그 라운드에 진출한(직전 라운드에서 이긴) 팀 전체와 정확히 일치해야 하고, 각 팀은 한 라운드에서 정확히 한 번만 경기한다.

각 줄에는 두 정수를 출력하며, 이는 두 팀이 그 경기에서 맞붙는다는 뜻이다.

우승이 가능한 대진표가 여러 개일 수 있으므로, 다음 규칙에 따른 사전순으로 가장 작은 대진표 하나만 출력한다.

• 한 경기를 한 줄에 출력할 때, 두 팀 번호 중 더 작은 값을 먼저 쓴다.
• 같은 라운드에 속한 경기들은 (첫 번째 수, 그다음 두 번째 수) 기준 오름차순으로 정렬해 출력한다.
• 두 대진표를 비교할 때는, 위 규칙대로 정렬하여 출력했을 때 위에서 아래로, 왼쪽에서 오른쪽으로 읽은 정수 수열을 사전순으로 비교한다. 이 수열이 더 작은 대진표를 답으로 한다.

여러 테스트 케이스의 출력은 사이에 빈 줄이나 구분선 없이 이어서 출력한다.