#include<bits/stdc++.h>
using namespace std;
const int N=100005,M=400005,K=30;
int T,n,q,a[N];
int nxt[N][K+2];
int L[M],R[M];
int ma[M][K+2];//ma[i][j]:a[i],从j位向高位运行,所有到过都为0,最多到哪
void pushup(int x)
{
	for(int j=0;j<=K;j++) ma[x][j]=max(ma[x*2][j],ma[x*2+1][j]);
}
void build(int l,int r,int x)
{
	L[x]=l,R[x]=r;
	if(l==r)
	{
		int pre=-1;
		for(int j=K;j>=0;j--)
		{
			if(a[l]&(1<<j)) ma[x][j]=-1,pre=j-1;
			else ma[x][j]=pre;
		}
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,x*2);
	build(mid+1,r,x*2+1);
	pushup(x);
}
int find(int l,int r,int x,int w)
{
	if(l<=L[x]&&R[x]<=r) return ma[x][w];
	int mid=(L[x]+R[x])/2;
	if(r<=mid) return find(l,r,x*2,w);
	if(l>mid) return find(l,r,x*2+1,w);
	return max(find(l,r,x*2,w),find(l,r,x*2+1,w));
}
int typ[K+2],wl,wr;
int use[N],cnt;
bool check(int l,int r)
{
	use[++cnt]=l-1;
	use[++cnt]=r+1;
	sort(use+1,use+cnt+1);
	for(int i=1;i<cnt;i++)
	{
		int fl=use[i]+1,fr=use[i+1]-1;
		if(fl>fr) continue;
//		printf("%d %d %d:%d\n",fl,fr,wl,find(fl,fr,1,wl));
		if(find(fl,fr,1,wl)>=wr) return true;
	}
	return false;
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&q);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int j=0;j<=K;j++) nxt[n+1][j]=n+1;
		for(int i=n;i>=1;i--)
			for(int j=0;j<=K;j++)
				if(a[i]&(1<<j)) nxt[i][j]=i;
				else nxt[i][j]=nxt[i+1][j];
		build(1,n,1);
		for(int i=1;i<=q;i++)
		{
			int l,r;
			scanf("%d%d",&l,&r);
			int ma=-1;
			for(int j=0;j<=K;j++)
			{
				if(nxt[l][j]>r){typ[j]=0;continue;}
				ma=j;
				int now=nxt[l][j];
				if(nxt[now+1][j]<=r){typ[j]=2;continue;}
				typ[j]=1;use[++cnt]=now;
			}
//			for(int j=0;j<=K;j++) printf("%d ",typ[j]);
			printf("%d ",(1<<ma+1)-1);
			wl=wr=-1;
			for(int j=0;j<=ma;j++) if(typ[j]==0) wr=j;
			for(int j=ma;j>=0;j--) if(typ[j]==0) wl=j;
			if(wl==-1&&wr==-1) printf("0\n");
			else if(check(l,r)) printf("1\n");
			else printf("2\n");
		}
	}
}