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})$.