Problem Description

Fusu is a maimai (舞萌) fan. In the next $n$ days, she will play maimai every day, and she hopes that the number of rounds she plays each day is the same.

Playing one round of maimai costs a fixed $1$ game coin. However, the price of game coins may change every day. Specifically, on day $i$, one yuan can buy $a_i$ game coins.

By doing black work for Luogu, Fusu will earn some income every day. She will earn $b_i$ yuan on day $i$.

Each day, Fusu will first receive that day’s income $b_i$, then buy game coins, and then play maimai.

Each day, Fusu may use any amount of the money she has to buy game coins at that day’s exchange rate. That is, she does not have to exchange all her money at once: she may spend only part of her money to buy game coins on that day, and save the remaining money for buying game coins in future days. Also, she does not have to spend all her game coins in one day: she may spend only part of them that day, and save the remaining game coins to play in later days.

Fusu knows the exchange rate and her income for each of the next $n$ days. She wants to play the same number of rounds of maimai every day during these $n$ days. Therefore, she wants to know: under an optimal strategy for buying game coins, what is the maximum number of rounds she can play per day?

Input Format

This problem contains multiple test cases within a single test point. The first line contains a positive integer $T$, the number of test cases. For each test case:

The first line contains an integer $n$, the total number of days.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$, where $a_i$ is the number of coins that 1 yuan can buy on day $i$.
The third line contains $n$ integers $b_1, b_2, \dots, b_n$, where $b_i$ is Fusu’s income on day $i$.

Output Format

For each test case, output one line with one integer, the answer.

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

Hint

Constraints

Let $N$ be the sum of $n$ over all test cases in a single test point.

• For $20\%$ of the data, $1 \leq n \leq 3$, $N \leq 1000$.
• For $40\%$ of the data, $1 \leq n \leq 2000$, $N \leq 10000$.
• For $60\%$ of the data, $1 \leq n \leq 10^5$, $N \leq 2 \times 10^5$.
• Another $10\%$ of the data satisfies $a_i \geq a_{i+1}$ for $1 \leq i \leq n-1$.
• Another $10\%$ of the data satisfies $a_i \leq a_{i+1}$ for $1 \leq i \leq n-1$.
• For $100\%$ of the data, $1 \leq n \leq 10^6$, $1 \leq a_i \leq 1000$, $1 \leq b_i \leq 10^9$, $n \leq N \leq 2 \times 10^6$, $1 \leq T \leq 2 \times 10^6$.

Translated by ChatGPT 5