#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int T,testid;
int n,m,c;
int a[500005];

struct fenwick{
	#define lowbit(x) (x & (-x))
	int tree[500005],bas;
	void init(){
		bas = 0;
		rep(i,1,m) tree[i] = lowbit(i);
	}
	void upd(int pos,int C){
		while(pos <= m){
			tree[pos] += C;
			pos += lowbit(pos);
		}
	}
	int qry(int pos){
		int ret = 0;
		while(pos){
			ret += tree[pos];
			pos -= lowbit(pos);
		}
		return ret;
	}
	int kth(int k){
		int pos = 0;
		per(_k,__lg(m),0){
			if(pos + (1 << _k) <= m && k > tree[pos + (1 << _k)]){
				pos += 1 << _k;
				k -= tree[pos];
			}
		}
		return pos + 1;
	}
	void rmv(int pos){
		upd(pos,-1);
		bas++;
	}
	int del(int k){
		if(bas >= k) return 0;
		int pos = kth(k - bas);
		rmv(pos);
		return pos;
	}
	int eval(int p){
		return bas + qry(p);
	}
}SS;

struct ds{
	int occ[500005],answer,pos;
	void init(){
		fill(occ,occ + m + 1,-1);
		answer = m;
		pos = m;
	}
	void rmv(int p){//[1,p) prefix add
		occ[p - 1]++;
		if(pos < p) answer++;
	}
	int eval(){
		if(pos >= 0) return answer;
		return -inf;
	}
	void dec(){
		pos--;
		if(pos >= 0) answer += occ[pos];
	}
}pst,nxt;

vector <int> S[2][500005];
void prepare(int op){
	SS.init();
	rep(i,1,n){
		int cur = a[i];
		while(1){
			int pos = SS.del(cur);
			if(!pos) break;
			S[op][i].eb(pos);
			cur -= c;
		}
	}
}

void eval(int V,int op,int *idx,int *res){
	fill(idx,idx + V + 1,n + 1);
	fill(res,res + V + 1,0);
	pst.init();nxt.init();
	int pos = m;
	rep(i,1,n){
		for(int p:S[op][i]) nxt.rmv(p);
		while(nxt.eval() > V){
			idx[pos] = i;
			res[pos] = V - pst.eval();
			pos--;nxt.dec();pst.dec();
		}
		for(int p:S[op][i]) pst.rmv(p);
	}
}

int idx[2][500005],res[2][500005];
int check(int V){
	eval(V,0,idx[0],res[0]);
	reverse(a + 1,a + n + 1);
	eval(V,1,idx[1],res[1]);
	rep(i,0,V) idx[1][i] = n + 1 - idx[1][i];
	reverse(a + 1,a + n + 1);

	rep(i,0,V){
		if(idx[0][i] > idx[1][V - i]) return 1;
		assert(idx[0][i] >= 1 && idx[0][i] <= n + 1);
		assert(idx[1][i] >= 0 && idx[1][i] <= n);
		if(idx[0][i] == idx[1][V - i] && 1ll * c * (res[0][i] + res[1][V - i]) + V >= a[idx[0][i]]) return 1;
	}
	return 0;
}

void solve(){
	scanf("%d%d%d",&n,&m,&c);
	rep(i,1,n){
		scanf("%d",&a[i]);
		S[0][i].clear();S[1][i].clear();
	}
	prepare(0);
	reverse(a + 1,a + n + 1);
	prepare(1);
	reverse(a + 1,a + n + 1);

	int answer = m;
	per(k,20,0) if(answer >= (1 << k) && check(answer - (1 << k))) answer -= 1 << k;
	printf("%d\n",answer);
//	check(2);
}

int main(){
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	scanf("%d%d",&T,&testid);
	while(T--) solve();
	return 0;
}