#define N 1000000
bool np[N];
vector<int> primes;

void init() {
    for (int i = 2; i < N; ++i) {
        if (!np[i]) primes.push_back(i);
        for (int v : primes) {
            if (v * i >= N) break;
            np[v * i] = true;
            if (i % v == 0) break;
        }
    }
}

bool np[N];
int phi[N], Min_factor[N], plist[N / 10];
void initPrime() {
  cnt = 0;
  phi[1] = 1;
  int x;
  for (int i = 2; i < N; i++) {
    if (!np[i]) {
      plist[cnt++] = i;
      phi[i] = i - 1;
      Min_factor[i] = i;
    }
    for (int k = 0; k < cnt && plist[k] * i < N; k++) {
      x = plist[k] * i;
      np[x] = true;
      Min_factor[x] = plist[k];
      if (i % plist[k] == 0) {
        phi[x] = phi[i] * plist[k];
        break;
      } else {
        phi[x] = phi[i] * (plist[k] - 1);
      }
    }
  }
}