#include <iostream>
#include <vector>
#include <chrono>
using namespace std;
using namespace std::chrono;
const int kMaxN = 1e8;
vector<int> phi(kMaxN + 1, 0);
void CalcPhi2() {
phi[1] = 1;
for (int n = 2; n <= kMaxN; ++n) {
if (phi[n] != 0) continue;
long long diff = n - 1;
for (long long p = n; p <= kMaxN; p *= n) {
for (int c = 0; c * p * n <= kMaxN; ++c) {
long long val = c * p * n;
for (int k = 1; k < n && p * (c * n + k) <= kMaxN; ++k) {
if (phi[c * n + k] == 0) continue;
phi[val + p * k] = phi[c * n + k] * diff;
}
}
diff *= n;
}
}
}
void CalcPhi3() {
phi[1] = 1;
for (int n = 2; n <= kMaxN; ++n) {
if (phi[n] != 0) continue;
int diff = n - 1;
for (long long p = n; p <= kMaxN; p *= n) {
for (int c = 1; c * p <= kMaxN; c++) {
int val = c * p;
if (phi[c] == 0) continue;
phi[val] = diff * phi[c];
}
diff *= n;
}
}
}
int main()
{
auto start = high_resolution_clock::now();
CalcPhi3();
auto stop = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop - start);
int n;
cin >> n;
long long sum = 0;
for (int i = 1; i <= n; ++i) {
sum += phi[i];
if (i % 100 == 0) {
sum = 0;
}
}
if (sum != 0) {
cout << sum << " ";
}
cout << endl;
cout << "Time taken by function: " << duration.count() / 1000000. << " seconds" << endl;
return 0;
}