import math
import sys
from bisect import bisect_left
from functools import reduce
from math import gcd


LIMIT = 20_000
PRIME_SEARCH_LIMIT = 2_000_000


def sieve_primes(n):
    is_prime = bytearray(b"\x01") * (n + 1)
    if n >= 0:
        is_prime[0] = 0
    if n >= 1:
        is_prime[1] = 0

    r = int(math.isqrt(n))
    for i in range(2, r + 1):
        if is_prime[i]:
            start = i * i
            is_prime[start : n + 1 : i] = b"\x00" * (((n - start) // i) + 1)

    return [i for i in range(2, n + 1) if is_prime[i]]


def factorize(n, primes):
    factors = []
    x = n
    for q in primes:
        if q * q > x:
            break
        if x % q:
            continue
        exponent = 0
        while x % q == 0:
            x //= q
            exponent += 1
        factors.append((q, exponent))
    if x > 1:
        factors.append((x, 1))
    return factors


def divisors_from_factors(factors):
    divisors = [1]
    for prime, exponent in factors:
        previous = divisors[:]
        power = 1
        for _ in range(exponent):
            power *= prime
            for d in previous:
                divisors.append(d * power)
    divisors.sort()
    return divisors


def primitive_root(p, small_primes):
    factors = factorize(p - 1, small_primes)
    for g in range(2, p):
        ok = True
        for q, _ in factors:
            if pow(g, (p - 1) // q, p) == 1:
                ok = False
                break
        if ok:
            return g
    return -1


def is_prime_by_trial(n, primes):
    if n < 2:
        return False
    for q in primes:
        if q * q > n:
            return True
        if n % q == 0:
            return n == q
    return True


def smallest_transition_prime(p, quotient_order, target_gcd, discrete_log, primes):
    def works(q):
        if q == p:
            return False
        residue = q % p
        if residue == 0:
            return False
        return gcd(discrete_log[residue], quotient_order) == target_gcd

    for q in primes:
        if works(q):
            return q

    q = primes[-1] + 1
    if q % 2 == 0:
        q += 1
    while True:
        if is_prime_by_trial(q, primes) and works(q):
            return q
        q += 2


class PrimeSolution:
    def __init__(self, log10_value=0.0, factors=None):
        self.log10_value = log10_value
        self.factors = factors or []


def solve_prime(p, primes):
    if p == 2:
        return PrimeSolution()

    n = p - 1
    root = primitive_root(p, primes)
    assert root > 0

    discrete_log = [-1] * p
    x = 1
    for exponent in range(n):
        discrete_log[x] = exponent
        x = x * root % p

    divisors = divisors_from_factors(factorize(n, primes))
    index = {value: i for i, value in enumerate(divisors)}
    inf = float("inf")

    dp = [inf] * len(divisors)
    parent = [-1] * len(divisors)
    edge = [(0, 0)] * len(divisors)
    transition_cache = {}

    dp[index[1]] = 0.0
    for i, subgroup_size in enumerate(divisors):
        if not math.isfinite(dp[i]):
            continue

        quotient_order = n // subgroup_size
        for length in divisors:
            if length <= 1 or quotient_order % length != 0:
                continue

            target_gcd = quotient_order // length
            key = (quotient_order, target_gcd)
            q = transition_cache.get(key)
            if q is None:
                q = smallest_transition_prime(
                    p, quotient_order, target_gcd, discrete_log, primes
                )
                transition_cache[key] = q

            next_size = subgroup_size * length
            j = index[next_size]
            candidate = dp[i] + (length - 1) * math.log10(q)
            if candidate + 1e-24 < dp[j]:
                dp[j] = candidate
                parent[j] = i
                edge[j] = (length, q)

    finish = index[n]
    factors = []
    at = finish
    while parent[at] != -1:
        factors.append(edge[at])
        at = parent[at]
    factors.reverse()
    return PrimeSolution(dp[finish], factors)


def exact_value(solution):
    value = 1
    for length, q in solution.factors:
        value *= q ** (length - 1)
    return value


def scientific(log10_value):
    exponent = math.floor(log10_value)
    mantissa = 10.0 ** (log10_value - exponent)
    mantissa = math.floor(mantissa * 100000.0 + 0.5) / 100000.0
    if mantissa >= 10.0:
        mantissa /= 10.0
        exponent += 1
    return f"{mantissa:.5f}e{exponent}"


class Solver:
    def __init__(self):
        self.primes = sieve_primes(PRIME_SEARCH_LIMIT)
        self._cache = {}

    def S(self, p):
        solution = self._cache.get(p)
        if solution is None:
            solution = solve_prime(p, self.primes)
            self._cache[p] = solution
        return solution

    def log_T(self, limit):
        values = []
        for p in self.primes:
            if p >= limit:
                break
            values.append(self.S(p).log10_value)
        return math.fsum(values)


def validate():
    solver = Solver()

    assert exact_value(solver.S(2)) == 1
    assert exact_value(solver.S(5)) == 8

    t20 = 1
    for p in solver.primes:
        if p >= 20:
            break
        t20 *= exact_value(solver.S(p))
    assert t20 == 1_348_422_598_656

    assert scientific(solver.log_T(100)) == "1.37451e123"
    print("Validation checkpoints passed.", file=sys.stderr)
    return solver


def main():
    solver = validate()
    print(scientific(solver.log_T(LIMIT)))


if __name__ == "__main__":
    main()