#include <bits/stdc++.h>
#include "Memory2_lib.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 100 + 10;
int tab[N], lsr[N], il[N];
int curv[5], counter = 0;
int edg[5][5];
vector<int> lft;
pair<int, int> ans[N];

inline void Start(int n)
{
    lft.clear();
    for(int i = 0; i < 5; ++i)
    {
        curv[i] = -1;
        for(int j = 0; j < 5; ++j)
            edg[i][j] = -1;
    }
    for(int i = 0; i < 2 * n; ++i)
    {
        ans[i] = make_pair(-1, -1);
        lft.pb(i);
        tab[i] = -1;
        lsr[i] = -1;
        il[i] = 0;
    }
    reverse(lft.begin(), lft.end());
}

int Chk(int pos)
{
    int val = edg[pos][1];
    if(pos == 1) val = edg[pos][2];
    for(int i = 1; i <= 4; ++i)
        if(i != pos && edg[pos][i] != val)
            return -1;
    return val;
}

void Add(int v)
{
    int pos;
    for(int i = 4; i >= 1; --i)
        if(curv[i] == -1) pos = i;
    ++counter;
    curv[pos] = v;
    for(int j = 1; j <= 4; ++j)
    {
        if(j != pos && curv[j] != -1)
        {
            edg[pos][j] = Flip(v, curv[j]);
            edg[j][pos] = edg[pos][j];
        }
    }
}

void Del(int pos)
{
    --counter;
    curv[pos] = -1;
    for(int j = 1; j <= 4; ++j)
    {
        edg[pos][j] = -1;
        edg[j][pos] = -1;
    }
}

void Finish(int n)
{
    for(int i = 1; i <= 4; ++i)
        if(curv[i] != -1) lft.pb(curv[i]);
    //cout << "finish: " << lft.size() << "\n";
    //cout << lft[0] << " " << lft[1] << " " << lft[2] << "\n";
    for(int i = 0; i < n; ++i)
    {
        //cout << "il: " << i << " " << il[i] << "\n";
        if(il[i] != 1) continue;
        int xd = (int)lft.size() - 1;
        for(int j = 0; j < (int)lft.size() - 1; ++j)
        {
            if(Flip(lft[j], lsr[i]) == i)
            {
                xd = j;
                break;
            }
        }
        //cout << "lsr: " << lsr[i] << " " << lft[xd] << "\n";
        tab[lft[xd]] = i;
        swap(lft[xd], lft[(int)lft.size() - 1]);
        lft.pop_back();
    }
    for(int i = 0; i < n; ++i)
    {
        if(il[i] != 0)continue;
        tab[lft[0]] = i;
        tab[lft[1]] = i;
    }
}

void DoAnswer(int n)
{
    for(int i = 0; i < 2 * n; ++i)
    {
        if(ans[tab[i]].st == -1) ans[tab[i]].st = i;
        else ans[tab[i]].nd = i;
    }
    for(int i = 0; i < n; ++i)
        Answer(ans[i].st, ans[i].nd, i);
}

void Solve(int t, int n)
{
    if(n == 1)
    {
        Answer(0, 1, 0);
        return;
    }
    Start(n);
    for(int i = 0; i < 4; ++i)
    {
        Add(lft.back());
        lft.pop_back();
    }
    while(counter + (int)lft.size() >= 4)
    {
        vector<int> del;
        int xd = 0;
        for(int i = 1; i <= 4; ++i)
        {
            int x = Chk(i);
            //cout << "bas: " << i << " " << curv[i] << " " << x << "\n";
            if(x == -1)
            {
                xd = i;
                continue;
            }
            ++il[x];
            tab[curv[i]] = x;
            del.pb(i);
        }
        for(int i = 0; i < (int)del.size(); ++i)
        {
            lsr[tab[curv[del[i]]]] = curv[xd];
            Del(del[i]);
        }
        //cout << "ending: " << counter << " " << lft.size() << "\n";
        while((int)lft.size() > 0 && counter != 4)
        {
            //cout << "add: " << lft.back() << "\n";
            Add(lft.back());
            lft.pop_back();
        }
        //cout << "ending: " << counter << " " << lft.size() << "\n";
    }
    Finish(n);
    DoAnswer(n);
}