GCD

Problem Description

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

Input

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.

Output

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

Sample Input

1
5
1 2 4 6 7
4
1 5
2 4
3 4
4 4

Sample Output

Case #1:
1 8
2 4
2 4
6 1

Author

HIT

Source

2016 Multi-University Training Contest 1