#include<bits/stdc++.h>

#define MAXN 10005

int n,C=1,D=0;
std::vector<std::pair<int,int> > ans;
int a[MAXN];
std::vector<int> tmp;
int vis[MAXN];

void swp(int x,int y){
    if(x==y) return;
    if(x&y){
        for(int i=0;i<D;i++){
            if(!(C>>i)) break;
            if((1^(x>>i)&1)&&(1^(y>>i)&1)){
                int t=(1<<i);
                ans.push_back(std::make_pair(t,x));
                ans.push_back(std::make_pair(t,y));
                ans.push_back(std::make_pair(t,x));
                return (void)(std::swap(a[x],a[y]));
            }
        }    
    }
    ans.push_back(std::make_pair(x,y));
    std::swap(a[x],a[y]);
    return;
}

void run(){
    std::cin>>n;
    for(int i=1;i<=n;i++) std::cin>>a[i];
    for(int i=1;i<=n;i++) vis[i]=0;
    ans.clear();
    if(n==1){
        std::cout<<0<<'\n';
        std::cout<<0<<'\n';
        return;
    }else if(n==2){
        if(a[1]==1) std::cout<<0<<'\n'<<0<<'\n';
        else{
            std::cout<<0<<'\n'<<1<<'\n'<<"1 2"<<'\n';
        }
        return;
    }
    C=1,D=0;
    while(C<=n) C*=2,++D;
    std::cout<<(n==C-1&&a[n]!=n)<<'\n';
    for(int i=1;i<=n;i++){
        if(vis[i]) continue;
        int now=i;
        tmp.clear();
        while(!vis[now]){
            tmp.push_back(now);
            vis[now]=1;
            now=a[now];
        }
        if(tmp.size()==1) continue;
        bool hay=false;
        for(int j:tmp) hay|=(j==(C-1));
        if(hay){
            for(std::vector<int>::iterator it=tmp.begin();it!=tmp.end();++it){
                if(*it==C-1){
                    tmp.erase(it);
                    break;
                }
            }
        }
        for(int j=0;j<=tmp.size();j++){
            swp(1,tmp[j%tmp.size()]); 
        }
    }
    
    if(n==C-1&&a[n]!=n){
        int pos=a[n];
        swp(pos,1);
        swp(1,n); 
        swp(1,pos);       
    }

    std::cout<<ans.size()<<'\n';
    for(std::pair<int,int> x:ans){
        std::cout<<x.first<<' '<<x.second<<'\n';
    }

    return;
}

int T;
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0),std::cout.tie(0); 

    std::cin>>T;
    for(int i=1;i<=T;i++){
        run();
    }

    return 0;
}