#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int T,tid,n,m,c,a[N],pl[N],cl[N],pr[N],cr[N];
int fa[N],tr[N],nx[N],tot;
bool dl[N];
vector<pair<int,int> >ml[N],mr[N];
inline void upd(int x){
	for(x=m-x+1;x<=m;x+=x&-x)--tr[x];
}
inline int qryk(int k){
	int x=0,v=0;
	for(int i=18;~i;--i)if(x+(1<<i)<=m&&v+tr[x+(1<<i)]<k)
		x+=1<<i,v+=tr[x];
	return m-x;
}
void calc(int t,vector<pair<int,int> >*g){
	nx[t+1]=t;
	for(int i=t+1;i<=m;++i)dl[i]=true;
	for(int i=0;i<=t;++i)fa[i]=i,nx[i]=i-1,dl[i]=false;
	for(int i=1;i<=n;++i){
		int nv=t;
		for(int j=nx[t+1];~j&&(t-nv)*c+t<a[i];j=nx[j]){
			pl[j]=i,cl[j]=t-nv,--nv,dl[j]=true;
			nx[t+1]=nx[j];
		}
		for(auto [u,v]:g[i])if(!dl[u]&&!dl[v])
			nx[u]=nx[v],fa[v]=u;
	}
	for(int i=nx[t+1];~i;i=nx[i])pl[i]=n+1;
	for(int i=t;~i;--i)pl[i]=pl[fa[i]],cl[i]=cl[fa[i]];
}
void Calc(vector<pair<int,int> >*g){
	for(int i=1;i<=m;++i)tr[i]=(i&-i);
	tot=m+1;
	for(int i=0;i<=m+1;++i)nx[i]=i-1;
	for(int i=1;i<=n;++i){
		int p=m-a[i]+1;
		while(p<tot){
			int u=qryk(p),v=nx[u];
			nx[u]=nx[v];
			g[i].emplace_back(u,v);
			--tot,upd(v);
			p+=c;
		}
	}
}
bool check(int t){
	reverse(a+1,a+n+1);
	calc(t,mr);
	for(int i=0;i<=t;++i)pr[i]=n-pl[i]+1,cr[i]=cl[i];
	reverse(a+1,a+n+1);
	calc(t,ml);
	for(int i=0;i<=t;++i){
		if(pl[i]>pr[t-i])return true;
		if(pl[i]<pr[t-i])continue;
		if(t+(cl[i]+cr[t-i])*c>=a[pl[i]])return true;
	}
	return false;
}
void init(){
	for(int i=1;i<=n;++i)ml[i].clear(),mr[i].clear();
	reverse(a+1,a+n+1);
	Calc(mr);
	reverse(a+1,a+n+1);
	Calc(ml);
}
void solve(){
	scanf("%d%d%d",&n,&m,&c);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	init();
	int l=0,r=m;
	while(l<r){
		int mid=l+r>>1;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	printf("%d\n",l);
}
int main(){
	scanf("%d%d",&T,&tid);
	while(T--)solve();
	return 0;
}