题目描述

这是本题的简单版本，两个版本的区别是：在这个版本里，$1 \le n \le 2 \cdot 10^5$，并且对于 $1 \le i \le n$，有 $b_i = a_i$。

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

对于数组 $a$ 的每个下标 $i$（$1 \le i \le n$），你最多可以进行一次下面的操作：

选择一个不等于 $a_i$ 的整数 $m$，满足 $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)$。

你需要求出在满足条件的情况下，最多能进行多少次操作。

输入格式

每个测试包含多组数据。

第一行一个整数 $t$（$1 \le t \le 10^4$），表示测试数据组数。

每组数据第一行一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示数组长度。

每组数据第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）。

每组数据第三行 $n$ 个整数 $b_1, b_2, \dots, b_n$（$b_i = a_i$）。

保证所有测试数据的 $n$ 之和不超过 $2 \cdot 10^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

数据规模与约定

对于 $100\%$ 的数据，$2 \le n \le 2 \cdot 10^5$，$1 \le a_i \le 10^9$，$b_i = a_i$，$1 \le t \le 10^4$，所有测试数据的 $n$ 之和不超过 $2 \cdot 10^5$。

来源：Codeforces Round 1089 (Div. 2) 题目网址：https://codeforces.com/contest/2210/problem/C1