#include<bits/stdc++.h>
using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
	ost<<"{"<<p.first<<","<<p.second<<"}";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
	ost<<"{";
	for(int i=0;i<v.size();i++){
		if(i)ost<<",";
		ost<<v[i];
	}
	ost<<"}";
	return ost;
}

inline int topbit(unsigned long long x){
	return x?63-__builtin_clzll(x):-1;
}

inline int popcount(unsigned long long x){
	return __builtin_popcountll(x);
}

inline int parity(unsigned long long x){
	return __builtin_parity(x);
}

int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}

int extgcd(int a,int b,int &x,int &y){
	int g=a;
	x=1;
	y=0;
	if(b!=0){
		g=extgcd(b,a%b,y,x);
		y-=(a/b)*x;
	}
	return g;
}
int inv(int a,int m){
	int x,k;
	extgcd(a,m,x,k);
	return (x%m+m)%m;
}

void solve(){
	int A,X,B,Y,C;
	cin>>A>>X>>B>>Y>>C;



	//gcd(A,B,C)=1
	int tmp=gcd(gcd(A,B),C);
	A/=tmp;B/=tmp;C/=tmp;


	/*
	By=-Ax mod C
	gcd(B,C) | (Ax)
	gcd(B,C) | x   (<=  gcd(gcd(B,C),A)=1)
	A *=gcd(B,C)
	X/=gcd(B,C)
	A/=gcd(B,C);B/=gcd(B,C);C/=gcd(B,C);
	*/
	
	//gcd(B,C)=1
	tmp=gcd(B,C);
	X/=tmp;
	B/=tmp;C/=tmp;

	/*
	By=-Ax mod C
	y=-inv(B)Ax mod C
	h:=(-inv(B)A mod C)

	(x,hx mod C) (x=0,1,2,...)
	*/

	//gcd(A,C)=1
	tmp=gcd(A,C);
	Y/=tmp;
	A/=tmp;C/=tmp;

	if(C==1){
		cout<<X+Y<<endl;
		return;
	}

	/*
	gcd(h,C)=1
	*/

	int H=(C-inv(B,C))*A%C;

	int h=H,c=C;
	vint dx,dy,num;
	dy.pb(C-h);
	num.pb(1);

	/*
	(h,c)->(h-d,h)  (d=C%h)
		 ->(h-2d,h-d)->...->(g,g+d)  (g=h%d)

		gcd(g,g+d)=gcd(g,d)=gcd(h%d,d)=gcd(h,d)=gcd(h,c%h)=gcd(h,c)=1
	*/

	while(h){
		if(h==1){
			dy.pb(1);
			num.pb(1);
			break;
		}
		int d=c%h;
		int g=h%d;
		dy.pb(d);
		num.pb(h/d);
		h=g;
		c=g+d;
	}

	/*
	dx=-H^{-1} dy
	*/
	int coef=C-inv(H,C);
	rep(i,dy.size()){
		dx.pb(coef*dy[i]%C);
	}

	
	int lb=0,ub=X+Y+1;
	while(ub-lb>1){
		int mid=(ub+lb)/2;

		int x=0,y=C*mid;
		rep(i,dx.size()){
			if(x+dx[i]*num[i]*mid<=X){
				x+=dx[i]*num[i]*mid;
				y-=dy[i]*num[i]*mid;
				continue;
			}

			int k=(X-x)/dx[i];
			x+=dx[i]*k;
			y-=dy[i]*k;
			break;
		}
		if(y<=Y)lb=mid;
		else ub=mid;
	}
	cout<<lb<<endl;
}

signed main(){
	int T;cin>>T;
	while(T--)solve();
	return 0;
}
