도시 계획

경기도의 한 도시가 새 구역을 지어 도시를 넓히려고 한다. 도시는 여러 건축가를 불렀고, 그중 남서가 도로망 설계를 맡았다. 남서는 일을 줄이려고 구역 안의 지역을 잇는 도로를 모두 일방통행으로 놓았다. 두 지역 $A$와 $B$는 $A$에서 $B$로 가는 도로와 $B$에서 $A$로 가는 도로를 따로 놓아 양쪽으로 이을 수 있다.

설계도를 그려 보니 일방통행 때문에 어떤 지역에서 다른 지역으로 아예 갈 수 없는 경우가 나왔다. 남서는 각 지역 $j$마다 $j$에서 갈 수 있는 지역을 모두 적은 목록을 종이에 옮겼다. 이 목록을 도로망의 '갈 수 있는 지역 목록'이라고 부른다. $A$에서 $B$로 가는 길과 $B$에서 $C$로 가는 길이 있으면 $A$의 목록에는 $B$와 $C$가, $B$의 목록에는 $C$가 적힌다.

그런데 하드 디스크가 망가져 설계도가 모두 사라졌다. 남은 것은 책상 위의 종이 한 장, 즉 '갈 수 있는 지역 목록'뿐이다.

이 목록만으로 도로망을 되살리려고 한다. 같은 목록을 만드는 도로망은 여러 가지다. 그중 도로가 가장 적은 도로망을 구하여라.

첫 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 20$)가 주어진다. 각 테스트 케이스는 빈 줄로 구분된다.

각 테스트 케이스의 첫 줄에 지역의 개수 $n$ ($1 \le n \le 300$)이 주어진다. 지역에는 1번부터 $n$번까지 번호가 붙어 있다. 이어지는 $n$개의 줄에는 길이가 $n$인 문자열이 한 줄씩 주어진다. $i$번째 줄은 지역 $i$에서 갈 수 있는 지역을 나타낸다. 이 줄의 $j$번째 문자가 0이면 지역 $i$에서 지역 $j$로 갈 수 없고, 1이면 지역 $i$에서 지역 $j$로 가는 방법이 하나 이상 있다. 지역 $i$에서 지역 $i$로는 언제나 갈 수 있으므로 $i$번째 줄의 $i$번째 문자는 항상 1이다.

주어진 목록을 만드는 도로망이 적어도 하나 존재한다.

각 테스트 케이스마다 도로가 가장 적은 도로망을 출력한다. 그런 도로망은 여러 개일 수 있으므로 다음 규칙으로 정해지는 하나만 출력한다.

먼저 서로 오갈 수 있는 지역끼리 하나의 그룹으로 묶는다. 지역 $u$와 $v$는 $u$에서 $v$로 갈 수 있고 $v$에서 $u$로도 갈 수 있을 때 같은 그룹에 속한다. 그룹에 속한 지역 중 번호가 가장 작은 지역을 그 그룹의 대표라고 하자.

• 크기가 2 이상인 그룹에서, 속한 지역을 번호가 커지는 순서로 $v_1, v_2, \dots, v_k$라 하면 도로 $v_1 \to v_2$, $v_2 \to v_3$, $\dots$, $v_{k-1} \to v_k$, $v_k \to v_1$을 놓는다. 크기가 1인 그룹 안에는 도로를 놓지 않는다.
• 서로 다른 두 그룹 $A$와 $B$에 대해, $A$의 지역에서 $B$의 지역으로 갈 수 있고, $A$에서 갈 수 있으면서 $B$로도 갈 수 있는 제3의 그룹 $C$가 없으면 $A$의 대표에서 $B$의 대표로 가는 도로 하나를 놓는다.

첫 줄에 이렇게 놓은 도로의 개수 $m$을 출력하고, 이어지는 $m$개의 줄에 도로를 한 줄에 하나씩 $a_i$ $b_i$ 형식으로 출력한다. 이는 지역 $a_i$에서 지역 $b_i$로 가는 일방통행 도로를 뜻한다. 도로는 $a_i$가 작은 순서로, $a_i$가 같으면 $b_i$가 작은 순서로 정렬해 출력한다. 이 규칙으로 나오는 도로망의 도로 개수는 최소다.

연속한 두 테스트 케이스의 출력 사이에는 빈 줄을 하나 출력한다.