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

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

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

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

  • выбрать произвольное целое число $$$m$$$ ($$$\mathbf{m \neq a_i}$$$), такое что $$$1 \leq m \le 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 2\cdot 10^5$$$) — длину массива $$$a$$$.

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

Следующая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$, разделённых пробелами ($$$\color{red}{b_i = a_i}$$$).

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

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

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

Пример
Входные данные
4
7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
3
67 67 67
67 67 67
6
8 10 10 12 12 14
8 10 10 12 12 14
8
2 4 8 16 32 64 128 256
2 4 8 16 32 64 128 256
Выходные данные
6
0
2
1
Примечание

Для первого набора входных данных НОД всех подмассивов равен $$$1$$$. Следовательно, мы можем выполнить $$$6$$$ операций и изменить массив на $$$a' = [1, 1, 1, 1, 1, 1, 1]$$$. Можно показать, что в этом случае максимальное количество операций равно $$$6$$$.

Для второго набора входных данных обратите внимание, что все значения равны, и уменьшение любого значения приводит к уменьшению НОД подмассивов. Следовательно, может быть выполнено $$$0$$$ операций.

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