CODE:
#include<bits/stdc++.h>
using namespace std;
#define li long long int
#define vi vector
li ans, ok;
vi arr;
void bitmasking(li co, li rw, li lld, li rd)
{
if(rw==ok)
{
++ans; return;
}
li pos=ok&(~(rw|lld|rd));
while(pos)
{
li p=pos&-pos;
pos-=p;
bitmasking(co+1, (rw|p), (lld|p)<<1, (rd|p)>>1);
if(ans)
{
arr[(int)(log2(p))]=co;
return;
}
}
}
int main()
{
li t;
cin>>t;
li mark[101];
vi mem[101];
memset(mark, 0, sizeof mark);
while(t--)
{
li n;
cin>>n;
if(!mark[n]){
arr.clear();
arr.assign(n+1, 0);
ok=0, ans=0;
ok=(1<<n)-1;
bitmasking(1, 0, 0, 0);
for(li i=0;i<n; ++i)
mem[n].push_back(arr[i]);
mark[n]=1;
}
for(li i=0;i<n; ++i)
{
cout<<i+1<<" "<<mem[n][i]<<endl;
}
}
return 0;
}