题目描述

对于两个长度为 \(m\) 的数组 \(a, b\), 定义一次操作如下：

• 选择一个整数 \(i\) （\(1 \le i \le m\)）；
• 令

\[ g_i = \gcd(a_i, a_{i + 1}, \dots, a_m) \]

• 对于所有 \(i \le j \le m\)，执行更新： \(b_j \gets b_j - g_i\)。

每次操作的代价为 \(1\)。

给定两个长度为 \(n\) 的整数数组 \(a\) 和 \(b\)。

现在有 \(q\) 次询问，每次询问给你两个正整数 \(l, r\) （\(1 \le l \le r \le n\)），你需要考虑两个新的数组 \(a' = a[l, r], b' = b[l, r]\)。

你需要计算将数组 \(b'\) 中的数全部不为正的所需的 最小总代价。

输入格式

每个测试文件包含多组测试数据。

第一行包含一个整数 \(T\) （\(1 \le T \le 10^5\)），表示测试数据的组数。

对于每组测试数据：

第一行包含两个整数 \(n\) 和 \(q\) （\(1 \le n, q \le 2 \cdot 10^5\)） —— 数组长度和查询次数。

第二行包含 \(n\) 个整数 \(a_1, a_2, \dots, a_n\) （\(1 \le a_i \le 10^9\)） —— 数组 \(a\) 的初始元素。

第三行包含 \(n\) 个整数 \(b_1, b_2, \dots, b_n\) （\(0 \le b_i \le 10^9\)） —— 数组 \(b\) 的初始元素。

接下来的 \(q\) 行，每行包含两个整数 \(l\) 和 \(r\) （\(1 \le l \le r \le n\)） —— 查询的闭区间范围。

数据保证 \(\sum n \le 10^6, \sum q \le 10^6\)。

输出格式

对于每个查询，输出一个整数表示最小代价。

样例输入

1
10 10
6 12 18 40 50 60 105 120 135 150
10 20 30 40 50 60 70 80 90 100
5 8
1 3
7 10
6 6
4 7
1 6
2 10
2 4
4 4
5 6

样例输出

12
5
7
1
12
18
38
16
1
6