说明

本题不再额外提供样例文件。

题目背景

根据公开资料，奥特曼卡片主要可以分为两大类：

‌宇宙英雄奥特曼X档案‌：这一系列的卡片通常以奥特曼或怪兽的实拍照片为主，搭配其等级、攻击力、防御力等基本信息，更侧重于角色科普和收藏。以下简称此类卡为档案卡。

‌英雄对决‌：这一系列的卡片则更强调对战玩法，卡片上会标注明确的攻防数值，并设计了基于地形的对战规则，鼓励玩家通过数值计算和策略进行对战，兼具娱乐性和教育性。以下简称此类卡为对决卡。

这两种类型是市面上奥特曼卡牌的主要划分方式，涵盖了绝大多数产品。下述题目中，小明收集的奥特曼卡片均为这两种类型之一。

题目描述

小明迷上了收集奥特曼卡片，他每天都要收集一张奥特曼卡片。现在他已经收集了 $a$ 张档案卡和 $b$ 张对决卡。

在收集过程中，小明可以随时去卡牌店用 $d$ 张对决卡兑换成 $c$ 张档案卡。

在接下来，小明会继续每天收集一张卡片，但是他并不知道自己每天收集到的卡片是哪种类型的。

问：从现在开始，至少再经过多少天，小明就可以保证有 $e$ 张档案卡？

输入格式

第一行：一个整数 $T$，表示数据组数；

接下来 $T$ 行，每行表示一组数据，包含 $5$ 个整数 $a$、$b$、$c$、$d$、$e$。

输出格式

共 $T$ 行，每组数据的答案占一行。

输入样例

5
1 2 3 4 5
1 2 3 4 1
0 0 1 123456789 987654321
37804185 12929912 90 15 134343953
67170781 11712651 83 15 967769157

输出样例

6
0
121932631112635269
18960320
835788415

数据范围

100% 的数据：$1 ≤ T ≤ 10^4$, $0 ≤ a, b, e ≤ 10^9$, $1 ≤ c, d ≤ 10^9$。其中：

• 10% 的数据：$c = d = 1$
• 10% 的数据：保证答案不超过 10.
• 20% 的数据：$c = 2$，$d = 3$