#include<bits/stdc++.h>usingnamespace std;typedeflonglong ll;constint MOD =998244353;constint N =2e5+10;ll a[N];
ll b[N];//前i个数的相同的数的最大值intmain(){int t;cin >> t;while(t --){ll n, k, q;cin >> n >> k >> q;for(int i =1; i <= n; i ++){cin >> a[i];a[i]-= i;}//求每个区间为k的区间众数的数量//看到定长想到滑动区间map<ll, ll>ma, cnt;//记录数量for(int i =1; i <= n; i ++){if(cnt.count(ma[a[i]]))//相当于对右边界进行操作{cnt[ma[a[i]]]-=1;if(!cnt[ma[a[i]]]) cnt.erase(ma[a[i]]);}ma[a[i]]+=1;cnt[ma[a[i]]]+=1;//前k个数还没到达窗口最远if(i < k)continue;//因为区间长度已经确定为k了，因此我们确定了左区间，右区间也随之确定了b[i - k +1]= cnt.rbegin()->first;//代表反向开始的第一个元素，即众数// cout << b[1] << "sss" << endl;cnt[ma[a[i - k +1]]]-=1;//因为开始窗口滑动了因此也需要考虑左边界了if(!cnt[ma[a[i - k +1]]]) cnt.erase(ma[a[i - k +1]]);ma[a[i - k +1]]-=1;//左边界ma也要参与了if(ma[a[i - k +1]]) cnt[ma[a[i - k +1]]]+=1;}while(q --){ll l, r;cin >> l >> r;cout << k - b[l]<< endl;}}return0;}
