GCD

Give you a sequence of $N(N \leq 100, 000)$ integers : $a_{1},...,a_{n}(0 < a_{i} \leq 1000, 000, 000)$. There are $Q (Q \leq 100, 000)$ queries. For each query $l, r$ you have to calculate $gcd(a_{l},,a_{l+1},...,a_{r})$ and count the number of pairs$(l’, r’) (1 \leq l < r \leq N)$such that $gcd(a_{l’},a_{l’+1},...,a_{r’})$ equal $gcd(a_{l},a_{l+1},...,a_{r})$.

The first line of input contains a number $T$, which stands for the number of test cases you need to solve.

The first line of each case contains a number $N$, denoting the number of integers.

The second line contains $N$ integers, $a_{1},...,a_{n}(0 < a_{i} \leq 1000, 000, 000)$.

The third line contains a number $Q$, denoting the number of queries.

For the next $Q$ lines, i-th line contains two number , stand for the $l_{i}, r_{i}$, stand for the i-th queries.

For each case, you need to output “Case #:t” at the beginning.(with quotes, $t$ means the number of the test case, begin from 1).

For each query, you need to output the two numbers in a line. The first number stands for $gcd(a_{l},a_{l+1},...,a_{r})$ and the second number stands for the number of pairs$(l’, r’)$ such that $gcd(a_{l’},a_{l’+1},...,a_{r’})$ equal $gcd(a_{l},a_{l+1},...,a_{r})$.