题目背景

nyl的数学作业步骤太繁琐了，blnyld决定帮他改一改。

可能有的值没有用

题目描述

nyl一共写了n道题的复杂度分别为 $a_1,a_2,a_3,...,a_n$。 blnyld，可以将$a_i$复杂度改为$m(1≤m≤a_i)$。

记所有操作后得到的数组为 $a'$。

你只能在保证以下条件成立的情况下进行上述操作：

对任意 $1≤l<r≤n$，都有$gcd(a_l,...,a_r)=gcd(a'_l,...a'_r​)$。

其中，$gcd(x,y)$ 表示整数 $x$ 和 $y$ 的最大公约数。

输入

每个测试包含若干组用例。第一行输入测试用例数 $t(1≤t≤10^4)$。接下来依次给出各组测试用例。

每组用例的第一行输入一个整数 $n(2≤n≤2⋅10^5)$，表示数组 $a$ 的长度。

第二行输入 $n$ 个空格分隔的整数 $a_1,a_2,…,a_n(1≤a_i≤10^9)$。

第三行输入 $n$ 个空格分隔的整数 $b_1,b_2,…,b_n(1≤b_i≤10^9)$。

保证所有测试用例中 $n$ 之和不超过 $2⋅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

Limitation

1s, 1024KiB for each test case.