← 返回题目列表

AtCoder · agc045_f

F. 除以倍数

中文机器翻译题面 查看原题

分数: 1800 点

问题陈述

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\}.