using System; using System.Collections; using System.Collections.Generic; using System.Diagnostics; using System.IO; using System.Linq; using System.Numerics; using System.Runtime.InteropServices; using System.Text; using System.Text.RegularExpressions; using System.Threading.Tasks; using static System.Math; using static Math2; using static io; using static Utils; public class CP { public void Solve() { var X = Cin(); var F = Enumerable.Range(0, X + 1).ToArray(); for (int i = 1; i <= X; ++i) { for (int j = 1; j * i <= X; ++j) { --F[j * i]; } } var ans = new List < (int, int) > (); for (int i = 1; i <= X; ++i) { var A = i; var B = X - i; ans.Add((A, Abs(F[A] - F[B]))); } ans.Sort((a, b) => a.Item2 - b.Item2); var aans = new List(); foreach (var x in ans) { if (x.Item2 == ans[0].Item2)aans.Add(x.Item1); else break; } aans.Sort(); foreach (var x in aans)Put(x, X - x); } } public static class NumberTheory { public static Dictionary PrimeFactorization(long N) { var ret = new Dictionary(); for (long i = 2; i * i <= N; ++i) { int cnt = 0; while (N % i == 0) { cnt++; N /= i; } if (cnt != 0)ret[i] = cnt; } if (N >= 2)ret[N] = 1; return ret; } public static Dictionary FactoricalPF(int N) { var ret = new Dictionary(); for (int i = 2; i <= N; ++i) { int ni = i; for (int j = 2; j * j <= ni; ++j) { int cnt = 0; while (ni % j == 0) { ++cnt; ni /= j; } if (cnt == 0)continue; if (ret.ContainsKey(j)) ret[j] += cnt; else ret[j] = cnt; } if (ni >= 2) { if (ret.ContainsKey(ni)) ret[ni] += 1; else ret[ni] = 1; } } return ret; } public static List DivisorEnumrate(long N) { var ret = new List(); for (long i = 1; i * i <= N; ++i) { if (N % i == 0) { ret.Add(i); ret.Add(N / i); } } return ret; } public static List seive(int n) { var ret = new List(); bool[] isPrime = new bool[n + 1]; for (int i = 1; i <= n; ++i)isPrime[i] = true; isPrime[1] = false; for (int i = 1; i <= n; ++i) { int j = i; if (isPrime[i])ret.Add(i); else continue; while (j <= n) { j += i; if (j > n)continue; isPrime[j] = false; } } return ret; } public static bool isPrime(long n) { for (int i = 2; i * i <= n; ++i) { if (n % i == 0)return false; } return true; } } public static class Math2 { public const int INF = 1 << 29; public const long INFL = 1L << 60; public const long MOD = 1000000007; public const long MOD2 = 998244353; public static long Power(long a, long b, long MOD = 1000000007) //i^N { long res = 1; while (b > 0) { if ((b & 1) != 0)res = res * a % MOD; a = a * a % MOD; b >>= 1; } return res; } public static long Power2(long a, long b) //i^N { long res = 1; while (b > 0) { if ((b & 1) != 0)res = res * a; a = a * a; b >>= 1; } return res; } public static long GCD(long a, long b) { while (b > 0) { var r = a % b; a = b; b = r; } return a; } public static long LCM(long a, long b) => (b / GCD(a, b)) * a; public static long Comb(long n, long r, int MOD = 1000000007) { if (r > n - r)r = n - r; long Nume = 1; long Deno = 1; if (r > n - r)r = n - r; for (long i = 1; i <= r; ++i) { Deno = (Deno * i) % MOD; Nume = Nume * (n - i + 1) % MOD; } return (Nume * inv(Deno)) % MOD; } public static long Comb2(long n, long r) { long Nume = 1; long Deno = 1; if (r > n - r)r = n - r; for (long i = 1; i <= r; ++i) { Deno *= i; Nume *= n - i + 1; } return Nume / Deno; } public static long inv(long x, int MOD = 1000000007) { return Power(x, MOD - 2, MOD); } } public static class Utils { public static void Swap(ref T A, ref T B) { T x = A; A = B; B = x; } public static int DigitSum(string N) { int ret = 0; for (int i = 0; i < N.Length; ++i)ret += N[i] - '0'; return ret; } public static string ConvertBase(long N, int K) { StringBuilder ret = new StringBuilder(); while (N > 0) { var r = N % K; N /= K; ret.Append(r); } return new string(ret.ToString().ToCharArray().Reverse().ToArray()); } public static bool NextPermutation(IList lis, Comparison cmp) { int n = lis.Count; int i = n - 1; while (i - 1 >= 0) { if (cmp(lis[i - 1], lis[i]) < 0)break; --i; } if (i == 0)return false; int j = i; while (j + 1 < n) { if (cmp(lis[i - 1], lis[j + 1]) > 0)break; ++j; } (lis[i - 1], lis[j]) = (lis[j], lis[i - 1]); int k = i; int l = n - 1; while (k < l) { (lis[k], lis[l]) = (lis[l], lis[k]); ++k; --l; } return true; } public static bool NextPermutation(IList lis) => NextPermutation(lis, Comparer.Default.Compare); } public class PriorityQueue { List _item; public int Count { get { return _item.Count; } } bool _isascend { get; set; } public T Peek { get { return _item[0]; } } Comparison Comp; public PriorityQueue(bool IsAscend = true, IEnumerable list = null) : this(Comparer.Default.Compare, IsAscend, list) { } public PriorityQueue(Comparison cmp, bool IsAscend = true, IEnumerable list = null) { _item = new List(); _isascend = IsAscend; this.Comp = cmp; if (list != null) { _item.AddRange(list); Build(); } } private int Compare(int i, int j) => (_isascend ? -1 : 1) * Comp(_item[i], _item[j]); private void Swap(int i, int j) { var t = _item[i]; _item[i] = _item[j]; _item[j] = t; } private int Parent(int i) => (i - 1) >> 1; private int Left(int i) => (i << 1) + 1; public T Enqueue(T val) { int i = _item.Count; _item.Add(val); while (i > 0) { int p = Parent(i); if (Compare(i, p) > 0) Swap(i, p); i = p; } return val; } private void Heapify(int index) { for (int i = index, j; (j = Left(i)) < _item.Count; i = j) { if (j != _item.Count - 1 && Compare(j, j + 1) < 0)j++; if (Compare(i, j) < 0) Swap(i, j); } } public T Dequeue() { T val = _item[0]; _item[0] = _item[_item.Count - 1]; _item.RemoveAt(_item.Count - 1); Heapify(0); return val; } private void Build() { for (var i = (_item.Count >> 1) - 1; i >= 0; i--) Heapify(i); } public bool Any() => Count > 0; } class Program { static void Main(string[] args) { var CP = new CP(); CP.Solve(); } } public static class io { public static void Put(string a) => Console.WriteLine(a); public static void Put(params object[] i) => Put(string.Join(" ", i)); public static void Put(IEnumerable a) => Put(string.Join(" ", a)); public static void PutV(IEnumerable a) { foreach (var z in a)Put(z); } public static void YN(bool i) { if (i)Put("Yes"); else Put("No"); } public static string Str => Console.ReadLine(); public static string[] Strs => Str.Split(" "); public static bool IsTypeEqual() => typeof(T).Equals(typeof(U)); public static T ConvertType(U a) => (T)Convert.ChangeType(a, typeof(T)); public static T Cast(string s) { if (IsTypeEqual())return ConvertType(int.Parse(s)); else if (IsTypeEqual())return ConvertType(long.Parse(s)); else if (IsTypeEqual())return ConvertType(double.Parse(s)); else if (IsTypeEqual())return ConvertType(char.Parse(s)); else return ConvertType(s); } public static T[] Castarr(string[] s) { var ret = new T[s.Length]; int i = 0; if (IsTypeEqual()) { var list = new List(); foreach (var t in s) { foreach (var u in t) { list.Add(ConvertType(char.Parse(u.ToString()))); } } return list.ToArray(); } foreach (var t in s) { if (IsTypeEqual())ret[i++] = ConvertType(int.Parse(t)); else if (IsTypeEqual())ret[i++] = ConvertType(long.Parse(t)); else if (IsTypeEqual())ret[i++] = ConvertType(double.Parse(t)); else ret[i++] = ConvertType(t); } return ret; } public static T Cin() { var t = Strs; return (Cast(t[0])); } public static(T a1, U a2)Cin() { var t = Strs; return (Cast(t[0]), Cast(t[1])); } public static(T a1, U a2, V a3)Cin() { var t = Strs; return (Cast(t[0]), Cast(t[1]), Cast(t[2])); } public static(T a1, U a2, V a3, W a4)Cin() { var t = Strs; return (Cast(t[0]), Cast(t[1]), Cast(t[2]), Cast(t[3])); } public static(T a1, U a2, V a3, W a4, X a5)Cin() { var t = Strs; return (Cast(t[0]), Cast(t[1]), Cast(t[2]), Cast(t[3]), Cast(t[4])); } public static(T a1, U a2, V a3, W a4, X a5, Y a6)Cin() { var t = Strs; return (Cast(t[0]), Cast(t[1]), Cast(t[2]), Cast(t[3]), Cast(t[4]), Cast(t[5])); } public static(T a1, U a2, V a3, W a4, X a5, Y a6, Z a7)Cin() { var t = Strs; return (Cast(t[0]), Cast(t[1]), Cast(t[2]), Cast(t[3]), Cast(t[4]), Cast(t[5]), Cast(t[6])); } public static T[] Cinarr() { var t = Strs; return Castarr(t); } public static T[] CinV(int n) { var ret = new T[n]; for (int i = 0; i < n; ++i) { ret[i] = Cin(); } return ret; } public static T Change(this T x, Func f) { return f(x); } }