#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define db double
#define ve vector<int>
#define pa pair<int,int>
#define fr first
#define sd second
#define pb push_back
#define mp make_pair
#define MEM(a) memset(a,0,sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
inline ll read()
{
	char ch = getchar();
	ll s = 0, w = 1;
	while (ch < '0' || ch > '9') {if (ch == '-')w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = s * 10 + ch - '0'; ch = getchar();}
	return s * w;
}
#define N 100010
#define int ll
int T;
struct BIT
{
	vector<int>c;
	int n;
	BIT(int n0) {n = n0; c.assign(n + 1, 0);}
	BIT() {}
	void add(int x) {for (; x <= n; x += x & (-x))c[x]++;}
	int qry(int x) {int s = 0; for (; x; x -= x & (-x))s += c[x]; return s;}
} A[40];
struct qry
{
	int l, r, id, r0;
};
int l[N], r[N], Or[21][N];
int n, q;
int a[N], s1[N];
int ans1[N], ans2[N];
set<int>S[40];
int findl(int x, int i) {return (*S[i].lower_bound(x));}
int findr(int x, int i) {return *(--S[i].upper_bound(x));}
int qor(int l, int r)
{
	if (l > r)return 0;
	int t = __lg(r - l + 1);
	return Or[t][l] | Or[t][r - (1 << t) + 1];
}
void sol(int number)
{
	n = read(), q = read();
	FOR(i, 0, 30)A[i] = BIT(n);
	FOR(i, 0, 30) {S[i].clear(); S[i].emplace(0); S[i].emplace(n + 1);}
	FOR(i, 1, n)a[i] = read();
	FOR(i, 1, n)Or[0][i] = a[i];
	FOR(j, 1, 20)FOR(i, 1, n)if (i + (1 << j) - 1 <= n)Or[j][i] = Or[j - 1][i] | Or[j - 1][i + (1 << j - 1)];
	FOR(i, 1, n)
	{
		REP(j, 30, 0)if ((a[i] >> j) & 1)S[j].emplace(i);
	}
	vector<vector<pa>>ad(31); vector<vector<qry>>qr(31);

	FOR(i, 1, n)
	{
		FOR(l, 0, 30)if (((a[i] >> l) & 1) == 0)
		{
			int r = l;
			while (r <= 30 && (((a[i] >> r) & 1) == 0))r++;
			ad[l].pb({r - 1, i}); l = r;
		}
	}

	FOR(t, 1, q)
	{
		s1[t] = 0;
		l[t] = read(), r[t] = read();
		vector<int>sta(31, 0);
		int mx = -1;
		REP(i, 30, 0)
		{
			int x0 = findl(l[t], i), y0 = findr(r[t], i);
			if (x0 > r[t] || y0 < l[t]) {sta[i] = -1;}
			else
			{
				if (mx == -1)mx = i;
				if (x0 < y0)sta[i] = 0;
				else sta[i] = x0;
			}
		}
		if (mx == -1) {ans1[t] = ans2[t] = 0; continue;}
		ans1[t] = (1LL << (mx + 1)) - 1;
		int fl = 0;
		FOR(i, 0, mx)if (sta[i] == -1)fl = 1;
		if (!fl) {ans2[t] = 0; continue;}
		FOR(i, 0, mx)if (sta[i] > 0)
		{
			int x = sta[i];
			FOR(j, 0, 30)if ((1LL << j) <= a[x])
			{
				int tmpx = a[x] - (1LL << j);
				if ((tmpx | qor(l[t], x - 1) | qor(x + 1, r[t])) == ans1[t])fl = 0;
			}
		}
		if (!fl) {ans2[t] = 1; continue;}
		int ml = inf, mr = -inf;
		FOR(i, 0, mx)if (sta[i] == -1)
		{
			ml = min(ml, i);
			mr = max(mr, i);
		}
		int H = (1LL << mr + 1) - (1LL << ml);
		FOR(i, 0, mx)if (sta[i] > 0)
		{
			int fl = 0, x = sta[i];
			FOR(j, ml, mr)fl |= ((a[x] >> j) & 1);
			s1[t] += (fl == 0);
		}
		int S = 0;
		FOR(x, l[t], r[t])
		{
			int fl = 0;
			FOR(j, ml, mr)fl |= ((a[x] >> j) & 1);
			S += (fl == 0);
		}
		if (S > s1[t]) ans2[t] = 1;
		else ans2[t] = 2;
		// qr[ml].push_back((qry) {l[t], r[t], t, mr});
	}

	// FOR(i, 0, 30)
	// {
	// 	for (auto [j, x] : ad[i])
	// 	{
	// 		FOR(t, i, j)A[t].add(x);
	// 	}
	// 	for (auto tmp : qr[i])
	// 	{
	// 		int j = tmp.r0; int l = tmp.l, r = tmp.r, id = tmp.id;
	// 		int val = A[j].qry(r) - A[j].qry(l - 1);
	// 		// if (val < s1[id])
	// 		// {
	// 		// 	cerr << "??:" << l << " " << r << endl;
	// 		// 	FOR(i, l, r)cerr << a[i] << ' '; cerr << endl;
	// 		// 	exit(0);
	// 		// }
	// 		if (val > s1[id]) ans2[id] = 1;
	// 		else ans2[id] = 2;
	// 	}
	// }
	// FOR(i, 1, q)cout << ans1[i] << ' ' << ans2[i] << '\n';
	if (number == 2434)
	{
		cerr << n << endl;
		FOR(i, 1, n)cerr << a[i] << ' '; cerr << endl;
	}
}
signed main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	T = read(); int num = 0;
	while (T--)sol(++ num);
	return 0;
}
/*
1
2 2
924896435 917026400
1 2
1 2
2 2
*/