//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
ll a[100100];
struct block
{
	ll A,B,M;
	block(){}
	block(ll _A,ll _B,ll _M):A(_A),B(_B),M(_M){};
	inline ll length(){return (B-A+1)*M;}
	inline ll lget(ll x){return (x-1)/M+A;};
	inline ll rget(ll x){return lget(length()-x+1);}
	inline ll lgetd(ll x){return (x-1)/M*M+M-(x-1);}
	inline ll rgetd(ll x){return lgetd(x);}
	inline ll lgetd2(ll x){return (x-1)-(x-1)/M*M+1;}
	inline ll rgetd2(ll x){return lgetd2(x);}
};
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		ll m;
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			a[i]++;
		}
		sort(a+1,a+n+1);
		ll l=0,r=1e18;
		while(l<r)
		{
			ll tmp=m;
			ll mid=(l+r)/2;
			vector<block> vec;
			vector<pair<ll,ll>> vect;
			for(int i=1;i<=n;i++)
			{
				vect.pb(a[i],1);
				vect.pb(a[i]+(mid+(i&1))/2,-1);
			}
			int cnt=0;
			srt(vect);
			for(int i=0;i<sz(vect)-1;i++)
			{
				cnt+=vect[i].second;
				if(!cnt) continue;
				if(vect[i].first==vect[i+1].first) continue;
				if((vect[i+1].first-vect[i].first)<=m/cnt)
				{
					vec.pb(vect[i].first,vect[i+1].first-1,cnt);
					m-=(vect[i+1].first-vect[i].first)*cnt;
				}
				else
				{
					if(m/cnt)
						vec.pb(vect[i].first,vect[i].first+m/cnt-1,cnt);
					if(m%cnt)
						vec.pb(vect[i].first+m/cnt,vect[i].first+m/cnt,m%cnt);
					m=0;
				}
			}
			if(m)
			{
				m=tmp;
				l=mid+1;
				continue;
			}
			ll L=0,R=0;
			int lp=0,rp=sz(vec)-1;
			ll ans=0;
			while(lp<sz(vec))
			{
				if(L==vec[lp].length())
				{
					L=0;
					lp++;
					continue;
				}
				if(R==vec[rp].length())
				{
					R=0;
					rp--;
					continue;
				}
				ll len=min(vec[lp].length()-L,vec[rp].length()-R);
				ans=max(ans,vec[lp].lget(L+1)+vec[rp].rget(R+1));
				ans=max(ans,vec[lp].lget(L+len)+vec[rp].rget(R+len));
				if(vec[lp].M>=vec[rp].M)
					if(vec[lp].lgetd(L+1)<vec[rp].rgetd(R+1)&&vec[lp].lgetd(L+1)<=len-1)
						ans=max(ans,vec[lp].lget(L+1)+vec[rp].rget(R+1)+1);
				if(vec[lp].M<=vec[rp].M)
					if(vec[lp].lgetd2(L+len)>vec[rp].rgetd2(R+len)&&vec[rp].rgetd2(R+len)<=len-1)
						ans=max(ans,vec[lp].lget(L+len)+vec[rp].rget(R+len)+1);
				L+=len;
				R+=len;
			}
			if(ans<=mid)
				r=mid;
			else
				l=mid+1;
			m=tmp;
		}
		cout<<l<<'\n';
	}
	return 0;
}