你的跑步俱乐部里既有专业跑者，也有业余跑者。你安排了几次混合了专业跑者和业余跑者的训练跑。专业跑者的配速比业余跑者快，会将他们甩在身后。

你希望所有的跑者都能成为专业跑者，因此在安排训练跑时，你会仔细选择参加的专业跑者和业余跑者的人数。你知道，当一次训练跑中有 $x$ 名专业跑者和 $y$ 名业余跑者时，如果 $\frac{x}{x+y}$ 大于或等于阈值 $\frac{a}{b}$，那么在训练结束后，所有 $y$ 名业余跑者会因为感受到跟上专业跑者的压力，从而在今后转变为专业跑者。

计算你需要安排的最少训练跑次数，以将俱乐部中的所有成员都转变为专业跑者。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 100$)，表示测试用例的数量。

接下来的 $t$ 行，每行包含一个测试用例。每个测试用例包含四个整数 $n, k, a, b$ ($1 \le n, k, a, b \le 10^9$ 且 $a \le b$)，其中 $n$ 是专业跑者的人数，$k$ 是业余跑者的人数，$\frac{a}{b}$ 是将业余跑者转化为专业跑者的阈值。

输出格式

输出 $t$ 行，每行包含一个整数。对于每个测试用例，输出将所有业余跑者转化为专业跑者所需的最少训练跑次数。如果无法将所有业余跑者转化为专业跑者，则输出 $-1$。

样例

输入 1

3
9 5 5 6
2 7 1 8
3 4 1 5

输出 1

3
1
1