#include <bits/stdc++.h>
using namespace std;
const int L = 1e6 + 10;
long long int spf[L + 100];
map<long long int, long long int> x;
long long int soe() {
  long long int i, j;
  for (i = 1; i <= L; i++) spf[i] = i;
  for (i = 2; i * i <= L; i++) {
    if (spf[i] == i) {
      for (j = i * i; j <= L; j += i) {
        if (spf[j] == j) spf[j] = i;
      }
    }
  }
}
map<long long int, long long int> factorise(long long int x) {
  map<long long int, long long int> mq;
  while (x != 1) {
    mq[spf[x]]++;
    x = x / spf[x];
  }
  return mq;
}
int main() {
  ios_base::sync_with_stdio(false);
  long long int n, i;
  soe();
  return 0;
}
