int pr[N], pr_cnt, flg[N], mu[N], sum_mu[N];
void init() {
    mu[1] = 1;
    for (int i = 2; i < N; i ++) {
        if (!flg[i])pr[++pr_cnt] = i, mu[i] = -1;
        for (int j = 1; j <= pr_cnt && i*1ll * pr[j] < N; j ++) {
            flg[i * pr[j]] = 1;
            if (i%pr[j] == 0) {
                mu[i * pr[j]] = 0;
                break;
            }
            mu[i * pr[j]] = -mu[i];
        }
    }
    for (int i = 1; i < N; i ++) sum_mu[i] = sum_mu[i-1] + mu[i];
}