F. Kevin and Math Class
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Kevin is a student from Eversleeping Town, currently attending a math class where the teacher is giving him division exercises.

On the board, there are two rows of positive integers written, each containing $$$ n $$$ numbers. The first row is $$$ a_1, a_2, \ldots, a_n $$$, and the second row is $$$ b_1, b_2, \ldots, b_n $$$.

For each division exercise, Kevin can choose any segment $$$ [l, r] $$$ and find the smallest value $$$ x $$$ among $$$ b_l, b_{l+1}, \ldots, b_r $$$. He will then modify each $$$ a_i $$$ for $$$ l \leq i \leq r $$$ to be the ceiling of $$$ a_i $$$ divided by $$$ x $$$.

Formally, he selects two integers $$$ 1 \leq l \leq r \leq n $$$, sets $$$ x = \min_{l \leq i \leq r} b_i $$$, and changes all $$$ a_i $$$ for $$$ l \leq i \leq r $$$ to $$$ \lceil \frac{a_i}{x} \rceil $$$.

Kevin can leave class and go home when all $$$ a_i $$$ become $$$ 1 $$$. He is eager to leave and wants to know the minimum number of division exercises required to achieve this.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$ t $$$ ($$$ 1 \le t \le 10^4 $$$).

The first line of each test case contains an integer $$$ n $$$ ($$$ 1 \le n \leq 2 \cdot 10^5 $$$) — the length of the sequence $$$ a $$$ and $$$ b $$$.

The second line of each test case contains $$$ n $$$ integers $$$ a_1, a_2, \ldots, a_n $$$ ($$$ 1 \le a_i \le 10^{18} $$$) — the first row of integers on the board.

The third line of each test case contains $$$ n $$$ integers $$$ b_1, b_2, \ldots, b_n $$$ ($$$ 2 \le b_i \le 10^{18} $$$) — the second row of integers on the board.

It is guaranteed that the sum of $$$ n $$$ over all test cases doesn't exceed $$$ 2 \cdot 10^5 $$$.

Output

For each test case, output one integer — the minimum number of division exercises required to leave class.

Example
Input
3
3
5 4 2
6 3 2
5
3 6 1 3 2
3 5 3 2 2
6
8 3 3 7 5 8
3 2 3 4 2 3
Output
2
3
3
Note

For the first test case: $$$ [{\color{red}{5,4}},2]\xrightarrow[\min(b_1,b_2)=3]{\text{operate segment }[1,2]}[{\color{red}{2,2,2}}]\xrightarrow[\min(b_1,b_2,b_3)=2]{\text{operate segment }[1,3]}[1,1,1] $$$.

For the second test case: $$$ [{\color{red}{3,6,1}},3,2]\xrightarrow[\min(b_1,b_2,b_3)=3]{\text{operate segment }[1,3]}[1,{\color{red}{2,1,3}},2]\xrightarrow[\min(b_2,b_3,b_4)=2]{\text{operate segment }[2,4]}[1,1,1,{\color{red}{2,2}}]\xrightarrow[\min(b_4,b_5)=2]{\text{operate segment }[4,5]}[1,1,1,1,1] $$$.