题目描述

给你两个长度为 $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$，数组 $a$ 中从 $l$ 到 $r$ 的最大公约数，和数组 $a'$ 中从 $l$ 到 $r$ 的最大公约数完全相等。

请你求出最多能进行多少次操作。

输入格式

第一行一个整数 $t$，表示测试用例个数。

每个测试用例：

第一行一个整数 $n$，表示数组长度。

第二行 $n$ 个整数，表示数组 $a_1,a_2,\dots,a_n$。

第三行 $n$ 个整数，表示数组 $b_1,b_2,\dots,b_n$。

输出格式

对于每个测试用例，输出一行一个整数，表示最多能操作的次数。

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 \le t \le 10^4$

$2 \le n \le 5 \times 10^4$

$1 \le a_i,b_i \le 10^9$

所有测试用例的 $n$ 之和不超过 $5 \times 10^4$。

来源：Codeforces Round 1089 (Div. 2)

题目网址：https://codeforces.com/contest/2210/problem/C2