#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
using LL = long long;

struct List{
    vector<int> l, r;
    int n;

    List() = default;

    List(const vector<int> &p){
        n = int(p.size());
        l.resize(n + 2);
        r.resize(n + 2);
        for(int i = 0; i < n; i++){
            if (i == 0){
                r[p[i]] = p[i + 1];
                l[p[i]] = 0;
            }
            else if (i == n - 1){
                r[p[i]] = n + 1;
                l[p[i]] = p[i - 1];
            }
            else{
                r[p[i]] = p[i + 1];
                l[p[i]] = p[i - 1];
            }
        }
        r[0] = p.front();
        l[n + 1] = p.back();
    }

    void del(int x){
        r[l[x]] = r[x];
        l[r[x]] = l[x];
    }

    int back(){
        return l[n + 1];
    }

};

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<vector<int> > a(n, vector<int>(n));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                cin >> a[i][j];
            }
        }
        if (n == 1){
            continue;
        }
        vector<List> lst(n);
        for(int i = 0; i < n; i++) lst[i] = List(a[i]);
        vector<bool> del(n + 1);
        queue<int> q;
        for(int i = 0; i < n; i++){
            if (!del[lst[i].back()]){
                q.push(lst[i].back());
                del[lst[i].back()] = true;
            }
        }
        for(int i = 0; i < n - 1; i++){
            int t = q.front();
            q.pop();
            cout << t << ' ' << lst[t - 1].r[lst[t - 1].r[0]] << '\n';
            for(int j = 0; j < n; j++){
                lst[j].del(t);
                if (!del[lst[j].back()]){
                    q.push(lst[j].back());
                    del[lst[j].back()] = true;
                }
            }
        }
    }

}