#include <bits/stdc++.h>
using namespace std;

void solve(){
	int N, Q;
	cin >> N >> Q;
	vector<int> A(N);
	for(int i = 0; i < N; i++) cin >> A[i];
	vector<int> lis_length(N+1);
	auto get_lis = [&](int l, int r) -> int {
		vector<int> best = {};
		for(int i = l; i <= r; i++){
			int idx = (int)(lower_bound(best.begin(), best.end(), A[i]) - best.begin());
			if(idx == (int)best.size()) best.push_back(-1);
			best[idx] = A[i];
			lis_length[i+1] = (int)best.size();
		}
		return (int)best.size();
	};
	vector<int> best = {};
	for(int i = 0; i < N; i++){
		int idx = (int)(lower_bound(best.begin(), best.end(), A[i]) - best.begin());
		if(idx == (int)best.size()) best.push_back(-1);
		best[idx] = A[i];
		lis_length[i+1] = (int)best.size();
	}
	for(int q = 0; q < Q; q++){
		int l, r;
		cin >> l >> r;
		l--; r--;
		if(r-l <= 1100){
			cout << get_lis(l, r) << '\n';
		} else {
			cout << lis_length[r-l+1] << '\n';
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int T;
	cin >> T;
	while(T--) solve();
}
