C2. Простая задача на НОД (сложная версия)
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии $$$1 \leq n \leq 5 \cdot 10^{4}$$$, $$$1 \leq b_i \leq 10^{9}$$$ для всех $$$1 \leq i \leq n$$$, и ограничение по времени равняется $$$6$$$ секундам. Обратите внимание, что решение для одной версии не обязательно решает другую версию. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Вам даны два массива $$$a$$$ и $$$b$$$ длины $$$n$$$.

Для каждого индекса $$$i$$$ ($$$1 \le i \le n$$$) массива $$$a$$$ вы можете выполнить следующую операцию не более одного раза:

  • выбрать произвольное целое число $$$m$$$ ($$$\mathbf{m \neq a_i}$$$), такое что $$$1 \leq m \leq b_i$$$, и присвоить $$$a_i := m$$$.

Обозначим массив после выполнения всех операций как $$$a'$$$. Выполнять операции можно только так, чтобы выполнялось следующее условие:

  • для всех $$$1\leq l \lt r\leq n$$$ должно быть выполнено, $$$\operatorname{gcd}(a_l,a_{l+1},\ldots,{a_r})=\operatorname{gcd}(a'_l,a'_{l+1},\ldots,a'_r)$$$

Здесь $$$\gcd(x, y)$$$ обозначает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$.

Вам нужно определить максимальное количество операций, которое можно выполнить, сохранив это условие.

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

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

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \leq n \leq 5\cdot 10^4$$$) — длину массива $$$a$$$.

Следующая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$), разделённых пробелами.

Следующая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$, разделённых пробелами ($$$1 \le b_i \le 10^9$$$).

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

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

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

Пример
Входные данные
9
7
1 2 3 4 5 6 7
100 6 12 20 5 2 7
3
67 67 67
1000000000 1000000000 1000000000
6
8 10 10 12 12 14
1 1 1 1 1 1
8
2010 330 550 2 210 385 1001 323
2010 1000 1200 30 500 1000 2000 1000
4
1 2 4 3
1 1 1 1
6
2 3 4 5 1 6
10 15 20 25 5 30
2
1 2
2 100
5
2860 2860 143 9009 9009
2860 2860 1430 9009 9009
3
2 60 60
10 60 60
Выходные данные
7
3
0
7
1
6
2
0
0
Примечание

В первом наборе входных данных, поскольку НОД всех подмассивов равен $$$1$$$, мы можем преобразовать массив в $$$a' = [67, 5, 7, 11, 1, 2, 1]$$$. Здесь мы выполнили $$$7$$$ операций, и, поскольку в массиве всего $$$7$$$ элементов, это максимально возможное количество.

Во втором наборе входных данных мы можем преобразовать массив в $$$a' = [938, 2613, 4489]$$$. Можно показать, что после этого преобразования НОД всех подмассивов остаётся прежним. Следовательно, ответ равен $$$3$$$.

В третьем наборе входных данных можно показать, что не возможно выполнить ни одной операции, следовательно, ответ равен $$$0$$$.