#include<bits/stdc++.h>
using namespace std;
int n,q,a[100100],l1[101000][30],l2[101000][30][30];
void sol(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int j=0;j<30;j++)l1[n+1][j]=n+1;
    for(int j=0;j<30;j++)for(int k=j;k<30;k++)l2[n+1][j][k]=n+1;
    for(int i=n;i;i--){
        for(int j=0;j<30;j++)if((a[i]>>j)&1)l1[i][j]=i;else l1[i][j]=l1[i+1][j];
        int t=-1;
        for(int j=0;j<30;j++)for(int k=j;k<30;k++)
            l2[i][j][k]=l2[i+1][j][k];
        for(int j=0;j<30;j++)if((a[i]>>j)&1){
            for(int x=t+1;x<=j;x++)
            for(int y=x;y<=j;y++)
            l2[i][x][y]=i;
            t=j;
        }
    }
    for(int io=1,l,r;io<=q;io++){
        scanf("%d%d",&l,&r);
        int z=-1;
        for(int j=29;j>=0;j--)if(l1[l][j]<=r){z=j;break;}
        printf("%d ",(1<<(z+1))-1);
        vector<int>vp;vp.push_back(l-1),vp.push_back(r+1);
        int kl=32,kr=-1,st=0;
        for(int j=z;j>=0;j--)if(l1[l][j]<=r){
            st|=(1<<j);
            int x=l1[l][j];
            if(l1[x+1][j]>r)vp.push_back(x);
        }
        else kl=min(kl,j),kr=max(kr,j);
        if(kr==-1){puts("0");continue;}
        sort(vp.begin(),vp.end());
        bool oo=0;
        for(int j=0;j+1<vp.size();j++){
            int x=vp[j],y=vp[j+1];if(x==y||x+1==y)continue;
            x++,y--;
            if(l2[x][kl][kr]<=y){oo=1;break;}
        }
        for(int x:vp){
            if(x<l||x>r)continue;
            int sk=st;
            for(int i=0;i<30;i++)if(l1[l][i]==x&&l1[x+1][i]>r)sk^=(1<<i);
            for(int i=0;i<30;i++){
                if((1<<i)>a[x])break;
                if(sk^a[x]^(a[x]-(1<<i))==((1<<(z+1))-1))oo=1;
            }
        }
        if(oo)puts("1");else puts("2");
    }
}
int main(){
    int T;scanf("%d",&T);while(T--)sol();
    return 0;
}