#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define pii pair<int,int>
using namespace std;

const int maxn=500005;
const int inf=0x3f3f3f3f;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T--) {
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		if(b<=d&&c<=a+d-b) {
			cout<<(d-b)+(a+d-b-c)<<"\n";
		} else {
			cout<<"-1\n";
		}
	}
}

#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define pii pair<int,int>
using namespace std;

const int maxn=200005;
const int inf=0x3f3f3f3f;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T--) {
		int n;
		cin>>n;
		int sum0=0;
		bool f=false;
		for(int i=1;i<=n;i++) {
			int x;
			cin>>x;
			if(x==0) {
				sum0++;
			} else if(x>=2) {
				f=true;
			}
		}
		if(sum0<=(n+1)/2) {
			cout<<"0\n";
		} else if(f||sum0==n) {
			cout<<"1\n";
		} else {
			cout<<"2\n";
		}
	}
}

#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define pii pair<int,int>
using namespace std;

const int maxn=400005;
const ll inf=0x3f3f3f3f3f3f3f3f;

ll a[maxn];

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T--) {
		int n;
		cin>>n;
		ll ans=0,sum=0;
		for(int i=1;i<=n*2;i++) {
			cin>>a[i];
			ans+=abs(a[i]);
			sum+=abs(a[i]-(-1));
		}
		if(n==1) {
			ans=min(ans,abs(a[1]-a[2]));
		}
		if(n==2) {
			ans=min(ans,abs(a[1]-2)+abs(a[2]-2)+abs(a[3]-2)+abs(a[4]-2));
		}
		if(n%2==0) {
			for(int i=1;i<=n*2;i++) {
				ans=min(ans,sum-abs(a[i]-(-1))+abs(a[i]-n));
			}
		}
		cout<<ans<<"\n";
	}
}

#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define pii pair<int,int>
using namespace std;
 
const int maxn=500005;
const int inf=0x3f3f3f3f;
const int mod=998244353;

int a[maxn];
int f[maxn];

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T--) {
		int n;
		cin>>n;
		for(int i=1;i<=n-1;i++) {
			cin>>a[i];
		}
		f[1]=1;
		for(int i=1;i<=n-1;i++) {
			f[i+1]=1ll*f[i]*(i-a[i])%mod;
		}
		int ans=0;
		for(int i=1;i<=n-1;i++) {
			ans=(1ll*ans*i+(!a[i])*f[i])%mod;
			cout<<ans<<" ";
		}
		cout<<"\n";
	}
}

#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define pii pair<int,int>
using namespace std;

const int maxn=100005;
const int sqrtn=325;
const int B=320;
const int inf=0x3f3f3f3f;

int n,q;
int a[maxn];
int h[maxn];
int fa[maxn];
int cnt[maxn];
int depth[maxn];
ll f[maxn][sqrtn];
vector<int> tree[maxn]; 

void dfs(int x,int d) {
	h[x]=++cnt[d],depth[x]=d;
	for(int to:tree[x]) {
		dfs(to,d+1);
	}
}

ll ask(int x,int y) {
	if(!x&&!y) {
		return 0;
	}
	if(cnt[depth[y]]<=B&&f[x][h[y]]) {
		return f[x][h[y]];
	}
	ll ans=ask(fa[x],fa[y])+1ll*a[x]*a[y];
	if(cnt[depth[y]]<=B) {
		f[x][h[y]]=ans;
	}
	return ans;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
	}
	for(int i=2;i<=n;i++) {
		cin>>fa[i];
		tree[fa[i]].push_back(i);
	}
	dfs(1,0);
	while(q--) {
		int x,y;
		cin>>x>>y;
		cout<<ask(x,y)<<"\n";
	}
}

#include<bits/stdc++.h>
#define ll long long
#define int128 __int128
#define fir first
#define sec second
#define pii pair<int,int>
using namespace std;

const int maxn=1000005;
const ll inf=9e18;
const int128 inf128=(int128)(inf)*(int128)(inf);

ll a[maxn];
ll b[maxn];
ll g[maxn];
ll ra[maxn];
int128 suma[maxn];
int128 sumb[maxn];
int128 ans[maxn];

ll gcd(ll x,ll y) {
	return !y?x:gcd(y,x%y);
}

void print(int128 x) {
	if(!x) {
		return ;
	}
	print(x/10);
	cout<<(int)(x%10);
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T--) {
		int n,k;
		ll m;
		cin>>n>>m>>k;
		for(int i=1;i<=n;i++) {
			cin>>a[i];
		}
		sort(a+1,a+n+1);
		int t=0,r=0;
		for(int i=1;i<=n;i++) {
			if(i>1&&a[i]==a[i-1]) {
				b[++r]=a[i];
			} else {
				ra[++t]=a[i];
			}
		}
		n=t;
		for(int i=1;i<=n;i++) {
			a[i]=ra[i];
			g[i]=gcd(g[i-1],a[i]);
			suma[i]=suma[i-1]+a[i];
		}
		for(int i=0;i<=k;i++) {
			ans[i]=-inf128;
		}
		for(int l=1;l<=n;) {
			int r=l;
			while(r<=n&&g[r]==g[l]) {
				r++;
			}
			r--;
			ll Max=-inf;
			for(int i=r+1;i<=n;i++) {
				a[i]=gcd(a[i],g[l]);
				Max=max(Max,a[i]-ra[i]);
			}
			for(int i=r;i>=l;i--) {
				ans[i]=suma[n]-suma[i]+Max;	
				a[i]=gcd(a[i],g[l]);
				Max=max(Max,a[i]-ra[i]);
			}
			l=r+1;
		}
		for(int i=1;i<=r;i++) {
			sumb[i]=sumb[i-1]+b[i];
		}
		int128 final=-inf128;
		if(k<=r) {
			final=suma[n]+sumb[r]-sumb[k];
		}
		for(int i=0;i<=r&&i<=k;i++) {
			final=max(final,sumb[r]-sumb[i]+ans[k-i]);
		}
		print(final);
		cout<<"\n";
	}
}