You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

你有 𝑛个字母 𝐴，𝑚 个字母 𝐵，你可以将这些字母组成成为一个字符串，你需要使得这个字符串的权值尽量大。现在我们以如下规则计算这个字符串的权值。

1. 每有连续的 𝑎 个 𝐴 ，且下一个字母依旧是 𝐴，则权值 +1。假设 𝑎 = 3，且连续有 7 个 𝐴，那么根据此规则，权值 +2。你可以理解一段长度为 cntA 的 𝐴 所获得的权值为 $\lfloor \frac{cntA-1}{a} \rfloor$。
2. 每有连续的 𝑏个 𝐵，且下一个字母依旧是 𝐵，则权值 +1。
3. 上一个字母和当前字母不一样时，权值 +1。（第一个字母前面没有字母，也会使得权值+1，详见样例 1）

假设当前字母是 𝐵，则至少需要有连续 𝑐 个字母 𝐵，下一个字母才可以切换成 𝐴。字母 𝐴切换到字母 𝐵 没有任何限制。 请问你能构造的字符串权值最大可能是多少？

输入格式

输入第一行包含一个正整数 𝑡 表示测试的组数。 接下来每一行代表一个测试数据，给出五个正整数 𝑛, 𝑚, 𝑎, 𝑏,𝑐 ，意义如题面所 示。

输出格式

对于每一组输入数据，输出一行一个正整数表示答案。

6
1 1 1 1 1
5 4 3 3 2
5 5 3 3 2
3 9 3 3 3
7 3 3 5 8
4 7 2 8 5

2
5
6
8
4
5

提示与说明

###样例1 样例 1 可以设计为 AB 或者 BA，第一个字母前面没有字母，初始使得权值为 1，第二个字母和第一个不一样，权值 +1，总权值为 2。

样例 2 可以设计为ABBAAAABB ，也可以设计成 ABBAAABBA，权值均为 5。

样例3可以设计为ABBABBAAAB，权值为6

样例4可以设计为ABBBBABBBBAB,权值为8

样例5可以设计为AAAAAAABBB,权值为4

样例6可以设计为AAABBBBBABB。

P.S.防止抄错下面上图

数据范围

对于 20% 的数据，有 1 ≤ 𝑡 ≤ 5,1 ≤ 𝑛, 𝑚, 𝑎, 𝑏, 𝑐 ≤ 10。

对于 50% 的数据，有 1 ≤ 𝑡 ≤ 50,1 ≤ 𝑛, 𝑚, 𝑎, 𝑏, 𝑐 ≤ 100 对于 100% 的数据。

有 1 ≤ 𝑡 ≤ 50,1 ≤ 𝑛, 𝑚, 𝑎, 𝑏, 𝑐 ≤ $10^5$