给一个数列共n(n<=100,000)个数，a1,a2,...,an.(0<=ai<=1000,000,000).有q(q<=100,000)个询问。每个询问为l,r(1<=l<=r<=n).求gcd(al,al+1,...,ar).
再求区间[l,r]的子区间中(l<=l'<=r'<=r)满足gcd(al,al+1,...,ar) = gcd(al',al'+1,...ar')的子区间个数.
输入描述:
第一行一个数T表示数据组数
第二行一个数n
接下来一行n个数,a1,a2,...,an
接下一行一个数q
接下来一行2个数l和r。
输出描述:
首先输出一行“Case #:t”,t代表当前是第几组数据。
接下来q行，每行输出2个数，第一个是gcd(al,al+1,...,ar),
第二个是区间[l,r]的子区间中(l<=l'<=r'<=r)满足gcd(al,al+1,...,ar) = gcd(al',al'+1,...ar')的子区间个数。
示例1
输入
复制
2
5
1 2 4 6 7
4
1 5
2 4
3 4
4 4
5
1 2 4 2 1
6
1 1
1 3
2 2
2 3
2 4
3 3
输出
复制
Case #1:
1 8
2 4
2 1
6 1
Case #2:
1 1
1 3
2 1
2 2
2 5
4 1