Problem Description
You are given an array A , and Zhu wants to know there are how many different array B satisfy the following conditions?

  • 1≤Bi≤Ai
  • For each pair( l , r ) (1≤l≤r≤n) , gcd(bl,bl+1…br)≥2

Input
The first line is an integer T(1≤T≤10) describe the number of test cases.

Each test case begins with an integer number n describe the size of array A.

Then a line contains n numbers describe each element of A

You can assume that 1≤n,Ai≤105

Output
For the kth test case , first output “Case #k: ” , then output an integer as answer in a single line . because the answer may be large , so you are only need to output answer mod 109+7

Sample Input

1
4
4 4 4 4

Sample Output

Case #1: 17

解法：显然所有的GCD不等于1的数，都可以用素数和素数的组合的倍数来表达，那么1e5的数据大概有10000个素数，这里计算多少个数的GCD等于某个素数的组合显然需要容斥，但是如果容斥的时候直接O(n)计算，显然是会TLE的。我们可以用经典的剪枝，当我们处理的数为x的时候我们会发现a[i]/x的值会分成一段段相等的值，这就让我们想到通过a[i]/x来把a[i]分成块来算，然后每一块的答案就是长度的2^len，每一块相乘就是为GCD为x的答案，套上容斥就可以过啦。当然计算这个也是可以Mobius的啦。补充：这里对于GCD为x的时候答案就是每一个a[i]/x的乘积，直接算是O(n)的。

复杂度：O(10000*log10000*sqrt(10000))

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+7;
const int mod = 1e9+7;
int n, a[maxn];
LL qsm(int a, int k){
    LL res = 1, b = a;
    while(k){
        if(k&1) res=res*b%mod;
        b=b*b%mod;
        k>>=1;
    }
    return res;
}
int check(int k)
{
    LL ret=1;
    int t=1;
    while((t+1)*k<a[1]) t++;
    for(; t*k<=a[n]; t++){
        int l=lower_bound(a+1,a+n+1,t*k)-a;
        int r=lower_bound(a+1,a+n+1,(t+1)*k)-a;
        ret *= qsm(t, r-l);
        ret %= mod;
    }
    return ret;
}
int prime[maxn], tot;
LL ans;
bool isprime[maxn];
void init()
{
    memset(isprime, true, sizeof(isprime));
    for(int i=2; i<maxn; i++){
        if(isprime[i]){
            for(LL j=(LL)i*i; j<maxn; j+=i){
                isprime[j]=false;
            }
        }
    }
    for(int i=2; i<maxn; i++){
        if(isprime[i]){
            prime[++tot]=i;
        }
    }
}
void dfs(int now, int k, int jud)
{
    if(now > tot) return ;
    LL temp = k*prime[now];
    if(temp > a[1]) return;
    dfs(now+1, k, jud);
    ans = (ans + jud*check(temp)%mod + mod)%mod;
    dfs(now+1, temp, -jud);
}
int main()
{
    init();
    int T,ks=0;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d", &n);
        for(int i=1; i<=n; i++) scanf("%d", &a[i]);
        sort(a+1, a+n+1);
        ans=0;
        dfs(1,1,1);
        if(ans<0) ans+=mod;
        printf("Case #%d: %lld\n", ++ks, ans);
    }
    return 0;
}