题目描述

马克西姆（Maxim）和尼基塔（Nikita）正在合作完成一个包含 $n$ 行代码的项目。

马克西姆立刻开始工作，并以每小时 $x$ 行的速度编写代码，直到项目结束。

尼基塔有两个选择：

• 不使用 AI，从一开始就以每小时 $y$ 行的速度编写代码；
• 先花费 $z$ 小时设置 AI 代理，在此期间不编写任何代码，设置完成后以每小时 $10 \cdot y$ 行的速度编写代码。

尼基塔在工作开始前做出选择，并且之后不能更改。

在尼基塔设置 AI 期间，他完全不写代码，但马克西姆会继续以每小时 $x$ 行的速度工作。

当马克西姆和尼基塔共同编写的代码行数至少达到 $n$ 行时，项目被视为完成。如果项目在 AI 设置结束前就能完成，那么工作在那一刻结束。

时间以整小时计算：如果项目在一个小时的中途完成，这一个小时算作一个完整的小时（即向上取整）。

尼基塔会做出最优选择（选择是否使用 AI）。请确定项目完成所需的最少完整小时数。

输入格式

本题有多组数据

第一行输入一个整数 $t$ 表示测试数据组数。对于每一组数据：

• 仅包含一行四个整数 $n, x, y, z$，分别表示项目中的代码行数、马克西姆的速度、尼基塔不使用 AI 时的速度，以及设置 AI 所需的时间。

输出格式

对于每组测试数据，输出一行一个整数，表示如果尼基塔采取最优策略，项目完成所需的最少完整小时数。

10
1 1 1 1
2 1 1 5
3 1 1 1
110 10 9 1
54 14 1 1
30 8 1 13
6 2 1 3
82 4 5 7
200 3 2 4
76 211 743 432

1
1
2
2
3
4
2
8
13
1

数据规模与约定

对于 $100\%$ 的数据满足：$1 \le t \le 100$，$1 \le n, x, y, z \le 10^9$。

• 子任务 $1$ （$30$ 分）：$1 \le n,x,y,z \le 10000$。
• 子任务 $2$ （$30$ 分）：$z \ge n$。
• 子任务 $3$ （$40$ 分）：无特殊限制。