#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn=100000,LOG=16;

int te,n,Q,a[maxn+5];
int ST[LOG+1][maxn+5],sum[LOG+1][maxn+5];
int c[maxn+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
	static char buf[100000],*l=buf,*r=buf;
	return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
	T tot=0;char ch=readc(),lst='+';
	while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
	while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
	lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
struct fastO{
	int si;char buf[100000];
	fastO() {si=0;}
	void putc(char ch){
		if (si==100000) fwrite(buf,1,si,stdout),si=0;
		buf[si++]=ch;
	}
	~fastO() {fwrite(buf,1,si,stdout);}
}fo;
template<typename T> void writei(T x,char ch='\n'){
	int len=0,buf[100];
	if (x<0) fo.putc('-'),x=-x;
	do buf[len++]=x%10,x/=10; while (x);
	while (len) fo.putc(buf[--len]+48);
	if (ch) fo.putc(ch);
}
inline void Add(int x,int y) {for (;x<=n;x+=x&-x) c[x]=min(c[x],y);}
inline int Min(int x) {int MIN=n+1;for (;x;x-=x&-x) MIN=min(MIN,c[x]);return MIN;}
int main(){
	for (readi(te);te;te--){
		readi(n);readi(Q);
		for (int i=1;i<=n;i++) readi(a[i]);
		for (int j=0;j<=LOG;j++) ST[j][n+1]=n+1,sum[j][n+1]=0;
		for (int i=1;i<=n;i++) c[i]=n+1;
		for (int i=n;i;i--){
			ST[0][i]=Min(n-a[i]+1);
			sum[0][i]=(ST[0][i]>i+1);
			Add(n-a[i]+1,i);
		}
		for (int j=1;j<=LOG;j++)
			for (int i=1;i<=n;i++)
				ST[j][i]=ST[j-1][ST[j-1][i]],
				sum[j][i]=sum[j-1][i]+sum[j-1][ST[j-1][i]];
		for (int t=1,x,y;t<=Q;t++){
			readi(x);readi(y);
			int ans=0;
			for (int j=LOG;~j;j--) if (ST[j][x]<=y) ans+=sum[j][x],x=ST[j][x];
			if (x<y) ans++;
			printf("%d\n",ans);
		}
	}
	return 0;
}