题目描述

すぬけ君は $X+Y$ 個のボールを持っています． このうち $X$ 個には整数 $A$ が，残りの $Y$ 個には整数 $B$ が書かれています．

すぬけ君は，これらのボールをいくつかのグループに分けます． このとき，どのボールもちょうど $1$ つのグループに含まれ，またどのグループも $1$ つ以上のボールを含むようにします．

ここで，あるグループがよいグループであるとは，グループ内のボールに書かれている整数の総和が整数 $C$ の整数倍であることを意味します． よいグループの個数の最大値を求めてください．

$1$ つの入力につき，$T$ 個のテストケースに答えてください．

输入格式

入力は以下の形式で標準入力から与えられる． 入力の $1$ 行目は以下のとおりである．

$T$

そして，$T$ 個のテストケースが続く． これらはそれぞれ以下の形式で与えられる．

$A$ $X$ $B$ $Y$ $C$

输出格式

各テストケースについて，よいグループの個数の最大値を出力せよ． 各テストケースごとに改行せよ．

题目大意

东海帝皇在赢下日本达比，夺得第二冠后，获得了 $X+Y$ 个球。其中 $X$ 个球上写着整数 $A$ ，另外 $Y$ 个球上写着整数 $B$ 。

东海帝皇将这些球分成了若干组。每个球恰好只属于其中的一组，且每组球的个数可以为一个或者多个（不能没有） 。

如果一组球中所有写在球上的整数之和是整数 $C$ 的倍数时，则该组被称为 闪耀的组合 。

她现在想知道将这堆球进行分组之后，得到的组合中最多能有多少个 闪耀的组合 。

输入格式

第一行一个整数 $T$ 表示测试组数，然后接下来 $T$ 行，每行依次输入题干中的 $A$ , $X$ , $B$ , $Y$ , $C$

输出格式

共 $T$ 行，每行一个整数 $a$ 表示该组测试数据的答案

—— translated by

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

2
2
0

提示

制約

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

Sample Explanation 1

$1$ つ目のテストケースでは，$\{3,3,4\},\{3,4,4,4\}$ とグループ分けすれば，よいグループの個数が $2$ になります． $2$ つ目のテストケースでは，$\{2,1\},\{1,1,1\},\{1\}$ とグループ分けすれば，よいグループの個数が $2$ になります．