题目描述

Snuke 有 $X+Y$ 个球。其中 $X$ 个球上写着整数 $A$，另外 $Y$ 个球上写着整数 $B$。

Snuke 将这些球分成若干个组。每个球必须恰好被包含在一个组中，而且每个组中至少包含一个球。

如果一个组中所有球上的整数之和是一个整数 $C$ 的倍数，就说这个组是好的。求最多可以形成多少个好的组。

对于每个输入文件，解决 $T$ 个测试用例。

约束条件

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

输入

输入以标准输入格式给出，格式如下所示。第一行是：

$T$

接下来是 $T$ 个测试用例。每个测试用例的格式如下：

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

输出

对于每个测试用例，输出一行，包含最多可以形成的好的组的数量。

示例输入 1

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

示例输出 1

2
2
0

在第一个测试用例中，我们可以通过以下分组形成两个好的组：$\\{3,3,4\\}$ 和 $\\{3,4,4,4\\}$。

在第二个测试用例中，我们可以通过以下分组形成两个好的组：$\\{2,1\\}, \\{1,1,1\\}$ 和 $\\{1\\}$。