F. Кевин и математический класс
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Кевин — студент из Вечно Спящего Города, который в настоящее время посещает математический класс, где учитель задает ему упражнения на деление.

На доске написаны две строки положительных целых чисел, каждая из которых содержит $$$ n $$$ чисел. Первая строка — это $$$ a_1, a_2, \ldots, a_n $$$, а вторая строка — $$$ b_1, b_2, \ldots, b_n $$$.

Для каждого упражнения на деление Кевин может выбрать любой отрезок $$$ [l, r] $$$ и найти минимальное значение $$$ x $$$ среди $$$ b_l, b_{l+1}, \ldots, b_r $$$. Затем он изменит каждое $$$ a_i $$$ для $$$ l \leq i \leq r $$$ на округление вверх от $$$ a_i $$$, деленного на $$$ x $$$.

Формально, он выбирает два целых числа $$$ 1 \leq l \leq r \leq n $$$, устанавливает $$$ x = \min_{l \leq i \leq r} b_i $$$, и изменяет все $$$ a_i $$$ для $$$ l \leq i \leq r $$$ на $$$ \lceil \frac{a_i}{x} \rceil $$$.

Кевин может покинуть класс и вернуться домой, когда все $$$ a_i $$$ станут равны $$$ 1 $$$. Он стремится уйти и хочет узнать минимальное количество упражнений на деление, необходимых для достижения этого.

Входные данные

Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $$$ t $$$ ($$$ 1 \le t \le 10^4 $$$).

Первая строка каждого набора входных данных содержит целое число $$$ n $$$ ($$$ 1 \le n \leq 2 \cdot 10^5 $$$) — длина последовательностей $$$ a $$$ и $$$ b $$$.

Вторая строка каждого набора входных данных содержит $$$ n $$$ целых чисел $$$ a_1, a_2, \ldots, a_n $$$ ($$$ 1 \le a_i \le 10^{18} $$$) — первая строка целых чисел на доске.

Третья строка каждого набора входных данных содержит $$$ n $$$ целых чисел $$$ b_1, b_2, \ldots, b_n $$$ ($$$ 2 \le b_i \le 10^{18} $$$) — вторая строка целых чисел на доске.

Гарантируется, что сумма $$$ n $$$ по всем наборам входных данных не превышает $$$ 2 \cdot 10^5 $$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — минимальное количество упражнений на деление, необходимых для выхода из класса.

Пример
Входные данные
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
Выходные данные
2
3
3
Примечание

Для первого примера: $$$ [{\color{red}{5,4}},2]\xrightarrow[\min(b_1,b_2)=3]{\text{операция на отрезке }[1,2]}[{\color{red}{2,2,2}}]\xrightarrow[\min(b_1,b_2,b_3)=2]{\text{операция на отрезке }[1,3]}[1,1,1] $$$.

Для второго примера: $$$ [{\color{red}{3,6,1}},3,2]\xrightarrow[\min(b_1,b_2,b_3)=3]{\text{операция на отрезке }[1,3]}[1,{\color{red}{2,1,3}},2]\xrightarrow[\min(b_2,b_3,b_4)=2]{\text{операция на отрезке }[2,4]}[1,1,1,{\color{red}{2,2}}]\xrightarrow[\min(b_4,b_5)=2]{\text{операция на отрезке }[4,5]}[1,1,1,1,1] $$$.