import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

public class Euler995 {
    private static final int LIMIT = 20_000;
    private static final int PRIME_SEARCH_LIMIT = 2_000_000;

    private static int[] sievePrimes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        if (n >= 0) {
            isPrime[0] = false;
        }
        if (n >= 1) {
            isPrime[1] = false;
        }

        for (int i = 2; (long) i * i <= n; ++i) {
            if (!isPrime[i]) {
                continue;
            }
            for (long j = (long) i * i; j <= n; j += i) {
                isPrime[(int) j] = false;
            }
        }

        int count = 0;
        for (int i = 2; i <= n; ++i) {
            if (isPrime[i]) {
                ++count;
            }
        }

        int[] primes = new int[count];
        int at = 0;
        for (int i = 2; i <= n; ++i) {
            if (isPrime[i]) {
                primes[at++] = i;
            }
        }
        return primes;
    }

    private static ArrayList<int[]> factorize(int n, int[] primes) {
        ArrayList<int[]> factors = new ArrayList<>();
        int x = n;
        for (int q : primes) {
            if ((long) q * q > x) {
                break;
            }
            if (x % q != 0) {
                continue;
            }
            int exponent = 0;
            while (x % q == 0) {
                x /= q;
                ++exponent;
            }
            factors.add(new int[] {q, exponent});
        }
        if (x > 1) {
            factors.add(new int[] {x, 1});
        }
        return factors;
    }

    private static int[] divisorsFromFactors(ArrayList<int[]> factors) {
        ArrayList<Integer> divisors = new ArrayList<>();
        divisors.add(1);
        for (int[] factor : factors) {
            int prime = factor[0];
            int exponent = factor[1];
            ArrayList<Integer> previous = new ArrayList<>(divisors);
            int power = 1;
            for (int e = 1; e <= exponent; ++e) {
                power *= prime;
                for (int d : previous) {
                    divisors.add(d * power);
                }
            }
        }
        int[] out = new int[divisors.size()];
        for (int i = 0; i < divisors.size(); ++i) {
            out[i] = divisors.get(i);
        }
        Arrays.sort(out);
        return out;
    }

    private static long modPow(long base, int exponent, int mod) {
        long value = 1;
        long b = base % mod;
        int e = exponent;
        while (e > 0) {
            if ((e & 1) != 0) {
                value = value * b % mod;
            }
            b = b * b % mod;
            e >>= 1;
        }
        return value;
    }

    private static int primitiveRoot(int p, int[] smallPrimes) {
        ArrayList<int[]> factors = factorize(p - 1, smallPrimes);
        for (int g = 2; g < p; ++g) {
            boolean ok = true;
            for (int[] factor : factors) {
                int q = factor[0];
                if (modPow(g, (p - 1) / q, p) == 1) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                return g;
            }
        }
        return -1;
    }

    private static int gcd(int a, int b) {
        int x = Math.abs(a);
        int y = Math.abs(b);
        while (y != 0) {
            int t = x % y;
            x = y;
            y = t;
        }
        return x;
    }

    private static boolean isPrimeByTrial(long n, int[] primes) {
        if (n < 2) {
            return false;
        }
        for (int q : primes) {
            if ((long) q * q > n) {
                return true;
            }
            if (n % q == 0) {
                return n == q;
            }
        }
        return true;
    }

    private static int smallestTransitionPrime(
            int p,
            int quotientOrder,
            int targetGcd,
            int[] discreteLog,
            int[] primes) {
        for (int q : primes) {
            if (works(p, quotientOrder, targetGcd, discreteLog, q)) {
                return q;
            }
        }

        long q = primes[primes.length - 1] + 1L;
        if ((q & 1L) == 0) {
            ++q;
        }
        while (true) {
            if (isPrimeByTrial(q, primes)
                    && works(p, quotientOrder, targetGcd, discreteLog, q)) {
                return (int) q;
            }
            q += 2;
        }
    }

    private static boolean works(
            int p,
            int quotientOrder,
            int targetGcd,
            int[] discreteLog,
            long q) {
        if (q == p) {
            return false;
        }
        int residue = (int) (q % p);
        if (residue == 0) {
            return false;
        }
        return gcd(discreteLog[residue], quotientOrder) == targetGcd;
    }

    private static final class PrimeSolution {
        private double log10Value;
        private final ArrayList<int[]> factors = new ArrayList<>();
    }

    private static PrimeSolution solvePrime(int p, int[] primes) {
        PrimeSolution solution = new PrimeSolution();
        if (p == 2) {
            return solution;
        }

        int n = p - 1;
        int root = primitiveRoot(p, primes);
        if (root <= 0) {
            throw new IllegalStateException("primitive root not found");
        }

        int[] discreteLog = new int[p];
        Arrays.fill(discreteLog, -1);
        int x = 1;
        for (int exponent = 0; exponent < n; ++exponent) {
            discreteLog[x] = exponent;
            x = (int) ((long) x * root % p);
        }

        int[] divisors = divisorsFromFactors(factorize(n, primes));
        HashMap<Integer, Integer> index = new HashMap<>();
        for (int i = 0; i < divisors.length; ++i) {
            index.put(divisors[i], i);
        }

        double[] dp = new double[divisors.length];
        Arrays.fill(dp, Double.POSITIVE_INFINITY);
        int[] parent = new int[divisors.length];
        Arrays.fill(parent, -1);
        int[][] edge = new int[divisors.length][2];
        HashMap<Long, Integer> transitionCache = new HashMap<>();

        dp[index.get(1)] = 0.0;
        for (int i = 0; i < divisors.length; ++i) {
            int subgroupSize = divisors[i];
            if (!Double.isFinite(dp[i])) {
                continue;
            }

            int quotientOrder = n / subgroupSize;
            for (int length : divisors) {
                if (length <= 1 || quotientOrder % length != 0) {
                    continue;
                }

                int targetGcd = quotientOrder / length;
                long key = (((long) quotientOrder) << 32) ^ (targetGcd & 0xffffffffL);
                Integer cached = transitionCache.get(key);
                int q;
                if (cached == null) {
                    q = smallestTransitionPrime(
                            p, quotientOrder, targetGcd, discreteLog, primes);
                    transitionCache.put(key, q);
                } else {
                    q = cached;
                }

                int nextSize = subgroupSize * length;
                int j = index.get(nextSize);
                double candidate = dp[i] + (length - 1) * Math.log10(q);
                if (candidate + 1e-24 < dp[j]) {
                    dp[j] = candidate;
                    parent[j] = i;
                    edge[j][0] = length;
                    edge[j][1] = q;
                }
            }
        }

        int finish = index.get(n);
        solution.log10Value = dp[finish];

        ArrayList<int[]> reversed = new ArrayList<>();
        for (int at = finish; parent[at] != -1; at = parent[at]) {
            reversed.add(new int[] {edge[at][0], edge[at][1]});
        }
        for (int i = reversed.size() - 1; i >= 0; --i) {
            solution.factors.add(reversed.get(i));
        }
        return solution;
    }

    private static long exactValue(PrimeSolution solution) {
        long value = 1L;
        for (int[] factor : solution.factors) {
            int length = factor[0];
            int q = factor[1];
            for (int i = 1; i < length; ++i) {
                value *= q;
            }
        }
        return value;
    }

    private static String scientific(double log10Value) {
        long exponent = (long) Math.floor(log10Value);
        double mantissa = Math.pow(10.0, log10Value - exponent);
        mantissa = Math.floor(mantissa * 100000.0 + 0.5) / 100000.0;
        if (mantissa >= 10.0) {
            mantissa /= 10.0;
            ++exponent;
        }
        return String.format(java.util.Locale.ROOT, "%.5fe%d", mantissa, exponent);
    }

    private static final class Solver {
        private final int[] primes = sievePrimes(PRIME_SEARCH_LIMIT);
        private final HashMap<Integer, PrimeSolution> cache = new HashMap<>();

        private PrimeSolution s(int p) {
            PrimeSolution solution = cache.get(p);
            if (solution == null) {
                solution = solvePrime(p, primes);
                cache.put(p, solution);
            }
            return solution;
        }

        private double logT(int limit) {
            double total = 0.0;
            for (int p : primes) {
                if (p >= limit) {
                    break;
                }
                total += s(p).log10Value;
            }
            return total;
        }
    }

    private static Solver validate() {
        Solver solver = new Solver();

        assert exactValue(solver.s(2)) == 1L;
        assert exactValue(solver.s(5)) == 8L;

        long t20 = 1L;
        for (int p : solver.primes) {
            if (p >= 20) {
                break;
            }
            t20 *= exactValue(solver.s(p));
        }
        assert t20 == 1_348_422_598_656L;

        assert scientific(solver.logT(100)).equals("1.37451e123");
        System.err.println("Validation checkpoints passed.");
        return solver;
    }

    public static void main(String[] args) {
        Solver solver = validate();
        System.out.println(scientific(solver.logT(LIMIT)));
    }
}