题目名称：简单的 GCD 问题（简单版）

时间限制： 2 秒 | 内存限制： 512 MB

题目背景

这是该问题的简单版本。与困难版的区别在于：在此版本中，$1 \le n \le 2 \cdot 10^5$，且对于所有 $i$，满足 $b_i = a_i$。

题目描述

给你两个长度为 $n$ 的数组 $a$ 和 $b$。

对于数组 $a$ 中的每个下标 $i$ ($1 \le i \le n$)，你可以执行最多一次如下操作：

• 选择一个任意整数 $m$ ($m \neq a_i$)，满足 $1 \le m \le b_i$，并设定 $a_i := m$。

令操作后的数组为 $a'$。你执行操作的前提必须满足以下条件：

• 对于所有 $1 \le l < r \le n$，满足 $\gcd(a_l, a_{l+1}, \dots, a_r) = \gcd(a'_l, a'_{l+1}, \dots, a'_r)$。

任务： 计算在保持上述条件不变的情况下，最多可以对多少个位置执行操作。

输入格式

1. 第一行包含测试用例数量 $t$ ($1 \le t \le 10^4$)。
2. 每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$)，即数组长度。
3. 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)。
4. 第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（在简单版中，$b_i = a_i$）。
5. 保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行，表示最大可执行的操作次数。

样例分析