//f([l,r])=min_{i=l+k-1}^{r}(g[i])
#include <bits/stdc++.h>
#define ver 3
using namespace std;
const int N=200007;
typedef long long li;
const li inf=0xc0c0c0c0c0c0c0c0;
li a[N],g[N],ans[N];
template<int n,int m>struct matrix{
	li val[n][m];
	matrix(){memset(val,0,sizeof(val));}
	matrix(initializer_list<initializer_list<li>> x){
		int i=0,j=0;
		for(auto a:x){
			for(auto b:a) val[i][j++]=b;
			i++,j=0;
		}
	}
	li* operator[](const int x){return val[x];}
};
template<int n,int m>matrix<n,m> operator+(matrix<n,m> a,matrix<n,m> b){
	matrix<n,m> ans;
	for(int i=0;i<n;i++) for(int j=0;j<m;j++) ans[i][j]=a[i][j]+b[i][j];
	return ans;
}
template<int n,int m,int p>matrix<n,p> operator*(matrix<n,m> a,matrix<m,p> b){
	matrix<n,p> ans;
	for(int i=0;i<n;i++) for(int j=0;j<m;j++) {
		int x=a[i][j];
		for(int k=0;k<p;k++) ans[i][k]+=x*b[j][k];
	}
	return ans;
}
struct segtree1{
	int val[N<<3];
	#define ls(o) o*2
	#define rs(o) o*2+1
	void update(int o){val[o]=max(val[ls(o)],val[rs(o)]);}
	void build(int l,int r,int o){
		val[o]=0;
		if(l==r) return;
		int mid=(l+r)>>1;
		build(l,mid,ls(o)),build(mid+1,r,rs(o));
	}
	void add(int x,int ll,int rr,int o,int v){
		if(ll==rr) return void(val[o]+=v);
		int mid=(ll+rr)>>1;
		if(x<=mid) add(x,ll,mid,ls(o),v);
		if(x>mid) add(x,mid+1,rr,rs(o),v);
		update(o);
	}
} tt;
struct segtree{
	matrix<3,3> val[N<<2],lz[N<<2];
	#define ls(o) o*2
	#define rs(o) o*2+1
	void update(int o){val[o]=val[ls(o)]+val[rs(o)];}
	void build(int l,int r,int o){
		if(l==r) return void(val[o]=lz[o]={{1,0,0},{0,1,0},{0,0,1}});
		int mid=(l+r)>>1;
		build(l,mid,ls(o)),build(mid+1,r,rs(o));
		update(o);
	}
	void pushdown(int o){
		if(lz[o][0][1]||lz[o][2][0]||lz[o][2][1]){
			val[ls(o)]=val[ls(o)]*lz[o];
			val[rs(o)]=val[rs(o)]*lz[o];
			lz[o]={{1,0,0},{0,1,0},{0,0,1}};
		}
	}
	void add(int l,int r,int ll,int rr,int o,int v){
		if(l>r) return;
		if(l<=ll&&rr<=r) return void((val[o]=val[o]*matrix<3,3>({{1,1,0},{0,1,0},{v,v,1}}),lz[o]=lz[o]*matrix<3,3>({{1,1,0},{0,1,0},{v,v,1}})));
		pushdown(o);
		int mid=(ll+rr)>>1;
		if(l<=mid) add(l,r,ll,mid,ls(o),v);
		if(r>mid) add(l,r,mid+1,rr,rs(o),v);
		update(o);
	}
	matrix<3,3> query(int l,int r,int ll,int rr,int o){
		matrix<3,3> ans;
		if(l>r) return ans;
		if(l<=ll&&rr<=r) return val[o];
		pushdown(o);
		int mid=(ll+rr)>>1;
		if(l<=mid) ans=ans+query(l,r,ll,mid,ls(o));
		if(r>mid) ans=ans+query(l,r,mid+1,rr,rs(o));
		return ans;
	}
} tr;
struct query{int t,r;}; vector<query> q[N];
struct node{li pos,val;} st[N],*tp=st;
int main(){
	cin.tie(0)->sync_with_stdio(0);
	int t;
	cin>>t;
	while(t-->0){
		int n,k,qq;
		cin>>n>>k>>qq;
		for(int i=1;i<=n;i++) cin>>a[i],q[i].clear();
		tt.build(-n,n,1),tr.build(1,n,1);
		for(int i=1;i<k;i++) tt.add(a[i]-i,-n,n,1,1);
		for(int i=k;i<=n;i++){
			tt.add(a[i]-i,-n,n,1,1);
			g[i]=k-tt.val[1];
			tt.add(a[i-k+1]-i+k-1,-n,n,1,-1);
		}
		for(int i=1,l,r;i<=qq;i++)cin>>l>>r,q[l+k-1].push_back({i,r});
		tp=st;
		*(tp++)={n+1,inf};
		for(int i=n;i>=k;i--){
			while(tp!=st&&tp[-1].val>g[i]) tp--,tr.add(tp->pos,tp[-1].pos-1,1,n,1,g[i]-tp->val);
			tr.add(tp[-1].pos,n,1,n,1,0);
			*(tp++)={i,g[i]},tr.add(i,i,1,n,1,g[i]);
			for(auto j:q[i]) {
				auto x=tr.query(i,j.r,1,n,1);
				ans[j.t]=(ver==3?x[2][1]:x[2][0]);
			}
		}
		for(int i=1;i<=qq;i++) cout<<ans[i]<<'\n';
	}
}