F. 无人需要

单个测试点时间限制：$6$ 秒 单个测试点内存限制：$512$ 兆字节

奥列格收到了一个长度为 $n$ 的排列 $a$ 作为生日礼物。

他的朋友涅奇波尔问了奥列格 $q$ 个问题，每个问题由两个整数 $l$ 和 $r$ 描述。 奥列格需要回答有多少个下标集合 $(t_1,t_2,\dots,t_k)$（满足 $k\ge 1$）符合以下条件：

1. 对每个 $i$，都有 $l\le t_i\le r$；
2. 对每个 $i$，都有 $t_i<t_{i+1}$；
3. 对每个 $i$，都有 $a_{t_{i+1}}$ 能被 $a_{t_i}$ 整除。

请帮助奥列格回答所有问题。

输入格式

输入包含多组测试数据。

第一行一个整数 $t$（$1\le t\le 10^4$），表示测试用例数量。

每组测试数据： 第一行两个整数 $n,q$（$1\le n,q\le 10^6$），分别表示排列长度与询问次数。 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1\le a_i\le n$），表示排列 $a$。 接下来 $q$ 行，每行两个整数 $l,r$（$1\le l\le r\le n$），表示一组询问。

保证所有测试用例的 $n$ 之和与 $q$ 之和均不超过 $10^6$。

输出格式

对于每组测试数据，在一行内输出所有询问的答案，用空格隔开。

样例输入

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