Description

你有 $\mathit n$ 个字母 A，$\mathit m$个字母 B，你可以将这些字母组成成为一个字符串，你需要使得这个字符串的权值尽量大。现在我们以如下规则计算这个字符串的权值。

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

假设当前字母是 B，则至少需要有连续 $c$ 个字母 B，下一个字母才可以切换成 A。字母 A 切换到字母 B 没有任何限制。

请问你能构造的字符串权值最大可能是多少？

Format

Input

输入第一行包含一个正整数 $t$ 表示测试的组数。

接下来每一行代表一个测试数据，给出五个正整数 $n,m,a,b,c$，意义如题面所示。

Output

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

Samples

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

Explanation

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

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

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

对于样例 4，可以设计为 ABBBBABBBBAB，权值为 8。

对于样例 5，可以设计为 AAAAAAABBB，权值为 4。

对于样例 6，可以设计为 AAABBBBBABB。

Limitation

对于 20% 的数据，有 $1 \leq t \leq 5, 1 \leq n,m,a,b,c \leq 10$

对于 50% 的数据，有 $1 \leq t \leq 50, 1 \leq n,m,a,b,c \leq 100$

对于 100% 的数据，，有 $1 \leq t \leq 50, 1\leq n,m,a,b,c \leq 10^5$