两位英雄正在战斗，他们的名字分别是英雄 0 和英雄 1。

你控制英雄 0，你的敌人是英雄 1。每位英雄有五个整数属性：攻击力（ATTACK）、防御力（DEFENSE）、力量（POWER）、知识（KNOWLEDGE）和生命值（HEALTH）。当两位英雄对战时，他们将轮流进行攻击，你的英雄先手。每回合一名英雄恰好进行一次攻击，可以是物理攻击或魔法攻击。

假设他们的属性为 $A_i, D_i, P_i, K_i, H_i$ ($0 \le i \le 1$)。对于英雄 $i$，其物理攻击造成的伤害为 $C_p \cdot \max(1, A_i - D_{1-i})$，而其魔法攻击造成的伤害为 $C_m \cdot P_i$。其中 $C_p$ 和 $C_m$ 是给定的常数。

在英雄 $i$ 攻击后，$H_{1-i}$ 将减少相应的伤害值。如果 $H_{1-i}$ 小于或等于 0，则英雄 $(1-i)$ 战败，英雄 $i$ 获胜，战斗结束。

英雄 $i$ 在整场战斗中进行魔法攻击的次数不能超过 $K_i$ 次。

现在你知道你的敌人是一个完全不懂魔法的 Yog，这意味着 $P_1 = K_1 = 0$，且他只会进行物理攻击。你可以将 $N$ 个属性点任意分配给四个属性 $A_0, D_0, P_0, K_0$，这意味着这些属性可以是满足 $0 \le A_0 + D_0 + P_0 + K_0 \le N$ 的任意非负整数。

给定 $C_p, C_m, H_0, A_1, D_1$ 和 $N$，请计算你能构建出的英雄 0 在获胜的前提下，敌人英雄 1 的最大生命值 $H_1$。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。接下来是 $T$ 个测试用例。 每个测试用例仅包含一行，包含六个整数 $C_p, C_m, H_0, A_1, D_1, N$ ($1 \le C_p, C_m, H_0, A_1, D_1, N \le 10^6$)，即上述描述的属性。

输出格式

对于每个测试用例，输出一行一个整数：在能够获胜的前提下，敌人英雄 1 的最大生命值。

样例

输入 1

2
1 1 4 5 1 4
2 5 1 9 9 6

输出 1

4
25