Good Intervals

Task

For some $k \ge 1$, we say that the sequence of integers $v = [v_1, v_2, \ldots v_k]$ is good if $v_i$ is divisible by $i$ for every $i$ from $1$ to $k$.

You are given an integer sequence $A = [A_1, A_2, \ldots, A_N]$ of length $N$ and $Q$ queries of the form $l_i, r_i$, which represent the range of values $[A_{l_i}, A_{l_i+1}, \ldots, A_{r_i}]$ from the sequence.

For each query compute the number of subintervals of the given range which are good sequences (each subinterval is considered as an independent sequence, indexed from $1$).

Input data

The first line of the input file contains a single integer $T$, the number of test cases. $T$ test cases follow, each preceded by an empty line.

The first line of each test case contains a single integer $N$, the length of the sequence.

The second line of each test case contains $N$ space-separated integers $A_i$, the elements of the sequence.

The third line of each test case contains a single integer $Q$, the number of queries.

Each of the following $Q$ lines contain two integers $l_i, r_i$, the query intervals.

Output data

For each test case, output all query results, each on a separate line.

Constraints and clarifications

• $1 \le T \le 10$.
• $1 \le N, Q \le 100 \ 000$.
• $1 \le A_i \le 10^{18}$.
• $1 \le l_i \le r_i \le N$.
• The sum of $N$ and $Q$ over all test cases does not exceed $100 \ 000$.

Example

stdin

1

5
6 24 6 8 10
3
1 3
2 4
1 5

stdout

6
5
12

Explanation

In the sample case, consider the the second query corresponding to the range of values $[24, 6, 8]$.

• An example of a good subinterval is $[A_2, A_3] = [24, 6]$, because $24$ is divisible by $1$ and $6$ is divisible by $2$.
• An example of a subinterval which is not good is $[A_2, A_3, A_4] = [24, 6, 8]$, as $8$ is not divisible by $3$.

The $5$ good subintervals for this query are the sequences $[24]$, $[24, 6]$, $[6]$, $[6, 8]$ and $[8]$.