#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
const int N = 100010;
int n, q, a[N], sum[N][30][30], cnt[N][30], nxt[N][30], tmp[30];
int stk[35], top; vector<int> e[N];

void clear(){
    while(top) {e[stk[top]].clear(); top--;}
}

void init(){
    rep(i, 1, n){
        int t = -1;
        per(j, 29, 0){
            rep(k, 0, 29) sum[i][j][k] = sum[i - 1][j][k];
            if(a[i]>>j&1) t = j;
            cnt[i][j] = t;
            if(~t) sum[i][j][t]++;
        }
    }
    rep(i, 0, 29) nxt[n + 1][i] = n + 1;
    per(i, n, 1) rep(j, 0, 29)
        nxt[i][j] = (a[i]>>j&1) ? i : nxt[i + 1][j]; 
}

void solve(){
    scanf("%d%d", &n, &q);
    rep(i, 1, n) scanf("%d", &a[i]);
    init();
    while(q--){
        clear();
        int x, y; scanf("%d%d", &x, &y);
        int mx = 0, l = -1, r = -1;
        per(i, 29, 0) if(nxt[x][i] <= y) {mx = i; break;}
        printf("%d ", (1 << (mx + 1)) - 1);
        per(i, mx, 0) if(nxt[x][i] > y) {l = i; break;}
        rep(i, 0, mx) if(nxt[x][i] > y) {r = i; break;}
        if(!~l) {puts("0"); continue;}
        rep(i, 0, 29) tmp[i] = sum[y][r][i] - sum[x - 1][r][i];
        rep(i, 0, 29) if(nxt[x][i] <= y && nxt[nxt[x][i]][i] > y){
            int t = nxt[x][i];
            if(e[t].empty()) stk[++top] = t;
            e[t].push_back(i);
        }
        bool flag = 0;
        rep(i, 1, top){
            int t = stk[i];
            if(~cnt[t][r]) tmp[cnt[t][r]]--;
            if(e[t].size() == 1)
                if(cnt[t][r] == e[t][0] && cnt[t][r] > l){
                    flag = 1; break;
                }
        }
        if(flag) {puts("1"); continue;}
        per(i, 29, l) if(tmp[i]) {flag = 1; break;}
        puts(flag ? "1" : "2");
    }
}

int main(){
    int T; scanf("%d", &T); while(T--) solve();
    return 0;
}