题目描述

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

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$