#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <cstring>
#include <list>  
#include <cassert>
#include <climits>
#include <bitset>
#include <chrono>
#include <random>
using namespace std;

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
std::mt19937 rnd((int)std::chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

struct Seq { ll lx, dx, cnt; Seq() {} Seq(ll lx, ll dx, ll cnt) :lx(lx), dx(dx), cnt(cnt) {} };

ll egcd(ll a, ll b, ll &x, ll &y) {
	if (b == 0) { x = 1, y = 0; return a; }
	ll g = egcd(b, a%b, y, x); y -= x*(a / b); return g;
}

ll inv(ll a, ll mod) {
	ll x, y, g = egcd(a, mod, x, y);
	if (g != 1) return -1;
	assert(x >= -mod && x <= mod);
	if (x < 0) x += mod;
	if (x >= mod) x -= mod;
	return x;
}

vector<Seq> calcIncreasingModularMultiples(ll k, ll mod) {
	ll h = k, w = mod;
	vector<Seq> ret;
	ll num = 0, den = inv(k, mod);
	while (h > 0 && w > 0) {
		if (w >= h) {
			ll t = w / h;
			ret.PB(Seq(num*den%mod, h*den%mod, t));
			num = (num + t*h) % mod;
			w -= t*h;
		} else {
			h %= w;
			if (h == 0) h = w;
		}
	}
	//printf("%lld %lld:", k, mod); REPSZ(i, ret) printf(" [%lld,%lld,%lld]", ret[i].lx, ret[i].dx, ret[i].cnt); puts("");
	return ret;
}

ll divup(ll num, ll den) { return num >= 0 ? (num + den - 1) / den : num / den; }
ll divdn(ll num, ll den) { return num >= 0 ? num / den : (num - den + 1) / den; }

ll a, na, b, nb, c;

ll solve() {
	ll all_groups_are_multiple_of = gcd(a, b);
	ll min_possible_multiple_of_c = lcm(c, all_groups_are_multiple_of);
	a /= all_groups_are_multiple_of, b /= all_groups_are_multiple_of, c = min_possible_multiple_of_c / all_groups_are_multiple_of;
	assert(gcd(a, b) == 1);

	ll contribution_of_a_in_good_group_is_multiple_of = lcm(a, gcd(b, c));
	ll contribution_of_b_in_good_group_is_multiple_of = lcm(b, gcd(a, c));
	ll count_of_a_in_good_group_is_multiple_of = contribution_of_a_in_good_group_is_multiple_of / a; // = gcd(b,c) because gcd(a,b)=1
	ll count_of_b_in_good_group_is_multiple_of = contribution_of_b_in_good_group_is_multiple_of / b; // = gcd(a,c) because gcd(a,b)=1
	a *= count_of_a_in_good_group_is_multiple_of, na /= count_of_a_in_good_group_is_multiple_of;
	b *= count_of_b_in_good_group_is_multiple_of, nb /= count_of_b_in_good_group_is_multiple_of;
	a /= count_of_a_in_good_group_is_multiple_of, b /= count_of_a_in_good_group_is_multiple_of, c /= count_of_a_in_good_group_is_multiple_of;
	a /= count_of_b_in_good_group_is_multiple_of, b /= count_of_b_in_good_group_is_multiple_of, c /= count_of_b_in_good_group_is_multiple_of;
	assert(gcd(a, b) == 1 && gcd(a, c) == 1 && gcd(b, c) == 1);

	if (c == 1) return na + nb;
	// we want a*x+b*y=0 mod c -> y=-(a/b)*x mod c and we only need solutions x1<x2<...<xk with y1>y2>...>yk or equivalently (a/b)*x1<(a/b)*x2<...<(a/b)*xk
	ll binv = inv(b, c);
	assert(binv != -1);
	ll z = (ll)a*binv%c;
	vector<Seq> seq = calcIncreasingModularMultiples(z, c);

	// x1=lx+i*dx, x2=x1+dx, y1=-z*x1, y2=-z*x2 [x1<x2, y1>y2], let dy=y1-y2
	// s*(lx+i*dx)+(mi-s)*(lx+(i+1)*dx)<=na -> i*mi+(mi-s)<=(na-mi*lx)/dx
	// s*(ly-i*dy)+(mi-s)*(ly-(i+1)*dy)<=nb -> i*mi+(mi-s)>=(mi*ly-nb)/dy
	ll ret = 0;
	REPSZ(i, seq) {
		ll lx = seq[i].lx, dx = seq[i].dx;
		ll ly = c - z*lx%c, dy = z*dx%c;
		ll lo = 0, hi = na + nb + 1;
		while (lo + 1 < hi) {
			ll mi = lo + (hi - lo) / 2;
			ll lbound = divup(mi*ly - nb, dy), ubound = divdn(na - mi*lx, dx);
			bool ok = lbound <= ubound && ubound >= 0 && lbound <= seq[i].cnt*mi;
			if (ok) lo = mi; else hi = mi;
		}
		ret = max(ret, lo);
	}
	return ret;
}

void run() {
	scanf("%lld%lld%lld%lld%lld", &a, &na, &b, &nb, &c);
	printf("%lld\n", solve());
}

void stress() {
	REP(rep, 100000) {
		ll mod, k; while (true) { mod = rnd() % 1000 + 1, k = rnd() % mod; if (k == 0 || gcd(k, mod) != 1) continue; else break; }
		vector<Seq> seq = calcIncreasingModularMultiples(k, mod);
		vector<ll> have; REPSZ(i, seq) FORE(j, i == 0 ? 0 : 1, seq[i].cnt) have.PB(seq[i].lx + j*seq[i].dx);
		vector<ll> want; REPE(i, mod) { ll cur = (ll)i*k%mod; if (i != 0 && cur == 0) cur = mod; if (SZ(want) == 0 || cur > (ll)want.back()*k%mod) want.PB(i); }
		bool ok = SZ(have) == SZ(want); if (ok) REPSZ(i, have) if (have[i] != want[i]) ok = false;
		if (ok) { if (rep % 1000 == 999) printf("."); continue; }
		printf("err\n");
		printf("have:"); REPSZ(i, have) printf(" %lld", have[i]); puts("");
		printf("want:"); REPSZ(i, want) printf(" %lld", want[i]); puts("");
	}
}

int main() {
	int ncase; scanf("%d", &ncase); FORE(i, 1, ncase) run();
	//stress();
	return 0;
}


Measured memory_bytes: 3728