Tsetso likes to play with arrays.

An Array $A[1,2,\ldots,N]$ is said to be a Tsetso array if $A[1] \cdot A[N] = max(A_{1},A_{2},\ldots,A_{N-1},A_{N})$.

Bedo, his teammate, likes to solve problems so much, so Tsetso gave him an array A of $N \bf{distinct} integers A_{1}, A_{2}, \ldots, A_{N}$ and Q queries of the form [L, R] and asked him to count the number of Tsetso subarrays in the given range.

A subarray[L,R] is to be a Tsetso subarray if $A[L] \cdot A[R] = max(A_{L},A_{L+1},....,A_{R-1},A_{R})$.

Bedo spent a lot of time trying to solve it, but he couldn't, can you?

$\bf{Note}$: A sequence a is a subarray of a sequence b if a can be obtained from b by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

------ Input Format ------

• First-line will contain T, the number of test cases. Then the test cases follow.
• The first line of input contains two space-separated integers N and Q, the number of elements in the array, and the number of queries.
• The second line contains $N \bf{distinct} space-separated integers A_{1}, A_{2}, \ldots, A_{N}$.
• Then Q lines follow each line containing two space-separated integers L, R.

------ Output Format ------

For each query, output in a single line the number of Tsetso subarrays in the given range [L, R].

------ Constraints ------

$1 ≤ T ≤ 10$
$2 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{18} $
$1 ≤ Q ≤ 5 \cdot 10^{5}$
$1 ≤L ≤R ≤N$
- Sum of $N$ over all testcases is atmost $10^{5}$.
- Sum of $Q$ over all testcases is atmost $5 \cdot 10^{5}$.

----- Sample Input 1 ------
1
7 3
3 6 24 4 1 8 2
1 7
2 5
4 7
----- Sample Output 1 ------
7
4
4
----- explanation 1 ------
- All the valid subarrays are $[1,6],[2,4],[3,5],[4,5],[5,5],[5,6],[4,7]$.
- One of the invalid subarrays is $[1,3] , 3 \cdot 24 \neq max(3,6,24)$

见题面

见题面