GCD

Time Limit: 5000 ms Memory Limit: 462144 KiB

Problem Description

Give you a sequence of N(N≤100,000) integers : a1,...,an(0. There are Q(Q≤100,000) queries.
For each query l,r you have to calculate gcd(al,,al+1,...,ar) and count the number of pairs(l′,r′)(1≤lsuch that gcd(al′,al′+1,...,ar′) equal gcd(al,al+1,...,ar).

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, a1,...,an(0.

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 li,ri, 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(al,al+1,...,ar) and the second number stands for the number of pairs(l′,r′) such that gcd(al′,al′+1,...,ar′) equal gcd(al,al+1,...,ar).

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

Hint

Source

2016 Multi-University Training Contest 1