#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
using i64 = long long;

constexpr int N = 51000000;
int primes[3000847 + 2], pl;
int f[N + 1], *minp = f;//[N + 1];
//int f[N+1], minp[N+1];
bitset<N> vis, die;

void chmax(auto &a, auto b) { a = max(a, b); }
int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n;
	cin >> n;
	//cout << (sizeof(primes) + sizeof(f) + sizeof(minp)) / 1000000 << endl;

	for (int i = 2; i <= n * (n - 1) / 2; i++) {
		if (!minp[i]) {
			//primes.push_back(i);
			primes[pl++] = i;
			minp[i] = i;
		}
	
		for (int p : primes) {
			if (p > n * (n - 1) / 2 / i) {
				break;
			}
			minp[p * i] = p;
			if (i % p == 0) {
				break;
			}
		}
	}
	//fill(f, f + N + 1, 0);
	memset(f, 0, sizeof(f));
	//memset(f, sizeof(f), 0);

	for (int i = 1; i <= n; i++) {
		f[i] = -i;
	}

	//for (auto p : primes) {
	for (int i = 0;i < pl;++i) {
		int p = primes[i];
		for (int i = 1; p * i <= n * (n - 1) / 2; i++) {
			f[p * i] += f[i];
		}
	}

	for (int i = 1; i <= n * (n - 1) / 2; i++) {
		f[i] += f[i - 1];
		f[i] += n;
	}

	int m = n * (n - 1) / 2;

	int ans = 1;

	for (int i = 0;i <= m;++i) {
		if (die[i]) continue;
		int u = i;
		while (!vis[u]) {
			vis[u] = true;
			u = f[u];
			if (die[u]) break;
		}
		u = f[u];
		if (!die[u]) { 
			//DE(u);
			int c = 0, v = u;
			do {
				v = f[v];
				++c;
				DE(v);
			} while (v != u);
			ans = max(ans, c);
		}
		u = i;
		while (!die[u]) {
			die[u] = true;
			u = f[u];
		}
	}


//	for (int i = 1; i <= m; i++) {
//		if (vis[i] == 0) {
//			int u = i;
//			while (vis[u] != i) {
//				vis[u] = i;
//				u = f[u];
//			}
//			if (vis[u] == i) {
//				int c = 0, v = u;
//				do {
//					v = f[v];
//					c++;
//				} while (v != u);
//				ans = max(ans, c);
//			}
//		}
//	}

	cout << ans << '\n';
}