不需要任何人

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

Oleg 收到了一份长度为 $n$ 的排列 $a$ 作为生日礼物。

Oleg 的朋友 Nechipor 向他提出了 $q$ 个询问。每个询问由两个整数 $l,r$ 表示。对于每个询问，你需要求出满足下列条件的下标序列 $(t_1,t_2,\ldots,t_k)$ 的数量，其中 $k\ge 1$：

• 对所有 $1\le i\le k$，都有 $l\le t_i\le r$；
• 对所有 $1\le i<k$，都有 $t_i<t_{i+1}$；
• 对所有 $1\le i<k$，$a_{t_{i+1}}$ 能被 $a_{t_i}$ 整除。

请回答所有询问。

输入格式

第一行包含一个整数 $T$，表示测试用例数量。

对于每个测试用例：

• 第一行包含两个整数 $n,q$，分别表示排列长度和询问数量；
• 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，它们构成 $1$ 到 $n$ 的一个排列；
• 接下来 $q$ 行，每行包含两个整数 $l,r$，表示一个询问区间。

输出格式

对于每个测试用例，输出一行 $q$ 个整数，按输入顺序给出所有询问的答案。

样例输入

4
8 8
2 1 6 3 5 4 8 7
1 8
2 8
1 7
1 6
1 3
5 8
4 4
2 3
1 1
1
1 1
3 3
3 2 1
1 2
1 3
2 3
8 1
1 2 3 4 5 6 7 8
1 8

样例输出

20 15 18 12 5 5 1 3
1
2 3 2
27

数据范围

对于所有数据：

• $1\le T\le 10^4$；
• $1\le n,q\le 10^6$；
• $a$ 是 $1$ 到 $n$ 的一个排列；
• $1\le l\le r\le n$；
• 所有测试用例的 $n$ 之和不超过 $10^6$；
• 所有测试用例的 $q$ 之和不超过 $10^6$；
• 答案使用 64 位有符号整数保存。

各子任务独立计分。