题目描述

小红是一个游戏爱好者。在接下来的 $n$ 天里，她每天都要去玩一款街机游戏，并且她希望每天游玩的局数相同。

游玩一局游戏固定花费 $1$ 个游戏币。然而，游戏币每天的价格都有可能变化。具体来说，在第 $i$ 天，一元可以购买 $a_i$ 个游戏币。

小红每天都会有一些收入。她会在第 $i$ 天收入 $b_i$ 元。

每天，小红会先得到当天的收入 $b_i$ 元，再去购买游戏币，再游玩。

小红每天可以使用自己拥有的钱的任意金额按照当天的币价购买游戏币。也就是说，她不必一次性换光所有的钱，可以在当天只使用一部分钱购买游戏币，存下一些剩余的钱留在今后的若干天购买游戏币。同时，她一天不必花光所有的游戏币，可以只在当天花费一部分游戏币，存下一些剩余的游戏币在之后的若干天玩。

小红知道今后 $n$ 天的币价和她每天的收入，她想在接下来 $n$ 天里每天游玩相同局数的游戏。因此她想知道，在她使用最优策略购买游戏币的情况下，她每天最多可以游玩多少局游戏？

输入格式

本题单个测试点内有多组测试数据。第一行是一个正整数 $T$，表示数据组数。对每组数据：

第一行是一个整数 $n$，表示总天数。
第二行是 $n$ 个整数 $a_1, a_2, \dots ,a_n$，表示每天一元钱购买的币数。
第三行是 $n$ 个整数 $b_1, b_2, \dots ,b_n$，表示小红每天的收入。

输出格式

对每组测试数据，输出一行一个整数表示答案。

样例

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

5
2
55

提示

数据规模与约定

用 $N$ 表示单个测试点内 $n$ 的和。

• 对 $20\%$ 的数据，保证 $1 \leq n \leq 3$，$N \leq 1000$；
• 对 $40\%$ 的数据，保证 $1\le n \le 2000$，$N \leq 10000$；
• 对 $60\%$ 的数据，满足 $1\le n \le 10^5$，$N \leq 2 \times 10^5$；
• 另有 $10\%$ 的数据，满足 $a_i \geq a_{i + 1}$（对 $1 \leq i \leq n-1$）。
• 另有 $10\%$ 的数据，满足 $a_i \leq a_{i + 1}$（对 $1 \leq i \leq n-1$）。
• 对于 $100\%$ 的数据，满足 $1\le n\le 10^6$，$1\le a_i \le 1000$，$1\le b_i \le 10^9$，$n \leq N \leq 2 \times 10^6$，$1 \leq T \leq 2 \times 10^6$。