说明

有$A$，$B$两种怪兽，打死一只$A$怪兽需要$W_a$点能量，打死后可以获得$H_a$个金币；打死一只$B$怪兽需要$W_b$点能量，打死后可以获得$H_b$个金币。

每种怪兽都有无限只，现在你有$C$点能量，请问你最多能获得多少个金币？

输入格式

第一行输入一个$T$，表示有$T$组数据

接下来有$T$行，每行有5个数，分别代表$W_a$，$W_b$，$H_a$，$H_b$，$C$。

$1 \le T \le 20$，$1 \le W_a,W_b \le 1000000000$，$0 \le H_a,H_b,C \le 1000000000$

输出格式

对于每组数据，输出一个数代表最多能获得的金币个数

样例

2
1 2 10 19 10
2 3 10 14 11

100
54