public class Euler243 {
    static final int[] primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 };
    static long best = Long.MAX_VALUE;

    static void dfs(int primeIndex, int maxExp, long n, long phiN, long targetNum, long targetDen) {
        if (n >= best)
            return;

        // Use BigInteger-like or carefully avoid overflow.
        // n is up to ~10^10, targetDen is ~10^5, so product is ~10^15, fits in long.
        if (n > 1 && phiN * targetDen < targetNum * (n - 1)) {
            best = n;
            return;
        }

        if (primeIndex >= primes.length)
            return;

        long p = primes[primeIndex];
        long nMul = n;
        long phiMul = phiN;

        for (int exp = 1; exp <= maxExp; ++exp) {
            if (nMul > best / p)
                break;

            nMul *= p;
            if (exp == 1) {
                phiMul *= (p - 1);
            } else {
                phiMul *= p;
            }

            dfs(primeIndex + 1, exp, nMul, phiMul, targetNum, targetDen);
        }
    }

    public static String solve() {
        long targetNum = 15499;
        long targetDen = 94744;
        best = Long.MAX_VALUE;

        dfs(0, 64, 1, 1, targetNum, targetDen);

        return String.valueOf(best);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}