Problem: Snuke has X+Y balls. X of them have an integer A written on them, and the other Y of them have an integer B written on them.

Snuke will divide these balls into some number of groups. Here, every ball should be contained in exactly one group, and every group should contain one or more balls.

A group is said to be good when the sum of the integers written on the balls in that group is a multiple of an integer C. Find the maximum possible number of good groups.

Solve T test cases for each input file.

Constraints

* 1 \leq T \leq 2 \times 10^4
* 1 \leq A,X,B,Y,C \leq 10^9
* A \neq B

Input

Input is given from Standard Input in the following format. The first line is as follows:


T


Then, T test cases follow. Each test case is given in the following format:


A X B Y C


Output

For each test case, print a line containing the maximum possible number of good groups.

Example

Input

3
3 3 4 4 5
2 1 1 5 3
3 1 4 2 5


Output

2
2
0

Solution (in CPP):

Solution:
#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;
}