这是问题的简单版本。版本之间的差异在于,在此版本中,$$$1 \leq n \leq 2 \cdot 10^{5}$$$ 和 $$$b_i = a_i$$$ 对于 $$$1 \leq i \leq n$$$。请注意,一个版本的解决方案不一定能解决另一版本的问题。只有解决了该问题的所有版本,您才能破解。
给定两个数组 $$$a$$$ 和 $$$b$$$,长度为 $$$n$$$。
对于 各索引 $$$i$$$ ($$$1 \le i \le 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$$$ 的最大公约数(GCD)。
您必须确定 最大 在确保条件仍然满足的情况下可以执行的操作数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,输出可以在换行符上完成的最大操作数。
示例
输入复制
471 2 3 4 5 6 71 2 3 4 5 6 7367 67 6767 67 6768 10 10 12 12 148 10 10 12 12 1482 4 8 16 32 64 128 2562 4 8 16 32 64 128 256
输出复制
6021
注意
对于第一个测试用例,所有子数组的 GCD 为 $$$1$$$。因此,我们可以执行 $$$6$$$ 操作并将数组更改为 $$$a' = [1, 1, 1, 1, 1, 1, 1]$$$。可以看出,在这种情况下可以执行的最大操作数是$$$6$$$。
对于第二个测试用例,请注意所有值都相等,并且减少任何值都会导致子数组的 GCD 减少。因此,可以执行$$$0$$$操作。
对于第三个测试用例,可以证明最多可以执行$$$2$$$操作。