Hero of the Kingdom 是一款点击类冒险游戏，主角踏上了一段危险的旅程，去拯救他/她的父亲并成为王国的英雄。

游戏中的货币被称为金币（gold），可以用来购买各种补给甚至完成特定的任务。俗话说，赚钱永远不嫌多，我们的天才玩家 BaoBao 刚刚发现了一种致富的方法。在游戏中，有一个磨坊，店主以每袋 $p$ 金币的价格出售面粉。还有一个酒馆，酒保以每袋 $q$ 金币的价格收购面粉（$q > p$）。显而易见，BaoBao 可以从中赚取差价，但在两个地点之间移动以及点击购买和出售按钮也需要时间。

更具体地说，如果 BaoBao 一次从磨坊购买 $x$ 袋面粉，他将花费 $(ax + b)$ 秒和 $px$ 金币；如果 BaoBao 一次向酒馆出售 $x$ 袋面粉，他将花费 $(cx + d)$ 秒，但随后会赚取 $qx$ 金币。BaoBao 目前有 $m$ 金币，但由于他该睡觉了，他最多只能玩 $t$ 秒游戏。请计算他在游戏结束时最多能拥有的金币数量。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 500$)，表示测试数据的组数。对于每组测试数据：

第一行包含三个整数 $p, a, b$ ($1 \le p, a \le 10^9, 0 \le b \le 10^9$)。

第二行包含三个整数 $q, c, d$ ($p < q \le 10^9, 1 \le c \le 10^9, 0 \le d \le 10^9$)。

第三行包含两个整数 $m$ 和 $t$ ($1 \le m, t \le 10^9$)。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示 BaoBao 在最多 $t$ 秒后能拥有的最大金币数量。

样例

输入格式 1

3
5 2 3
8 1 5
14 36
5 2 0
8 1 3
17 6
100 1 0
10000 1 0
99 100000

输出格式 1

32
20
99

说明

对于第一个样例测试数据，一种最优策略是：

• BaoBao 首先从磨坊购买 2 袋面粉。这需要 $2 \times 2 + 3 = 7$ 秒，花费 $5 \times 2 = 10$ 金币。然后他将所有面粉卖给酒馆。这又需要 $1 \times 2 + 5 = 7$ 秒，但 BaoBao 赚取了 $8 \times 2 = 16$ 金币。BaoBao 现在有 $14 - 10 + 16 = 20$ 金币，剩余时间为 $36 - 7 - 7 = 22$ 秒。
• BaoBao 接着从磨坊购买 4 袋面粉。这需要 $2 \times 4 + 3 = 11$ 秒，花费 $5 \times 4 = 20$ 金币。然后他将所有面粉卖给酒馆。这又需要 $1 \times 4 + 5 = 9$ 秒，但 BaoBao 赚取了 $8 \times 4 = 32$ 金币。BaoBao 现在有 $20 - 20 + 32 = 32$ 金币，剩余时间为 $22 - 11 - 9 = 2$ 秒。
• 现在 BaoBao 没有时间购买或出售面粉了。因此答案是 32。

对于第二个样例测试数据，BaoBao 只有时间购买并出售一袋面粉。因此答案是 $17 - 5 + 8 = 20$。

对于第三个样例测试数据，BaoBao 没有足够的金币购买面粉。因此答案是 99。