# define _SCL_SECURE_NO_WARNINGS

# include <iostream>
# include <string>
# include <iomanip>
# include <stdio.h>
# include <array>
# include <numeric>
# include <algorithm>
# include <vector>
# include <functional>
# include <fstream>
# include <cmath>

namespace
{

    using Ull = unsigned long long;
    using Ll = long long;

    namespace mine
    {

        template<typename T>
        std::istream& operator >> (std::istream& is, std::vector<T>& vec)
        {
            for (T& x : vec) is >> x;
            return is;
        }

        template<typename T>
        std::string to_string(std::vector<T> vec, std::string sep = " ")
        {
            std::string result;
            for (T& x : vec) result += std::to_string(x) + sep;
            result.erase(result.size() - sep.length());

            return result;
        }

        template<typename T, size_t L>
        std::string to_string(T(&ary)[L], std::string sep = " ", size_t size = L)
        {
            std::string result;
            for (int i = 0; i < size; ++i) result += std::to_string(ary[i]);
            result.erase(result.size() - sep.length());

            return result;
        }

        template<typename T, size_t L, typename Function>
        void for_each(T(&ary)[L], Function lambda)
        {
            for (size_t i{}; i < L; ++i)
                lambda(static_cast<T&>(ary[i]));
        }

        template<typename T>
        void SetAll(T container, typename T::value_type value = typename T::value_type{})
        {
            for (typename T::reference content : container)
                content = value;
        }

        template<typename T, size_t L>
        void SetAll(T(&ary)[L], T value = T{})
        {
            for (size_t i{}; i < L; ++i)
                ary[i] = value;
        }

        template<typename T, size_t L>
        std::array<T, L> AsContainer(T(&ary)[L], bool isSwap = true)
        {
            std::array<T, L> result;

            if (isSwap)
            {
                for (size_t i{}; i < L; ++i)
                    std::swap(result[i], ary[i]);
            }
            else
            {
                for (size_t i{}; i < L; ++i)
                    result[i] = ary[i];
            }

            return result;
        }

        template<size_t length>
        constexpr std::array<size_t, length> range()
        {
            std::array<size_t, length> range{};

            for (size_t i{}; i < length; ++i)
                range[i] = i;

            return range;
        }

        template<typename T>
        const std::vector<T> range(const T length)
        {
            std::vector<T> range(length);

            for (T i{}; i < length; ++i)
                range[i] = i;

            return range;
        }

        template<typename T>
        const std::vector<T> range(const T start, const T end)
        {
            if (start == end) return std::vector<T>{};

            else if (start > end)
            {
                std::vector<T> range(start - end);

                for (T i{start}; i > end; --i)
                    range[start - i] = i;

                return range;
            }
            else
            {
                std::vector<T> range(end - start);

                for (T i{start}; i < end; ++i)
                    range[i - start] = i;

                return range;
            }
        }

        bool IsPrime(const Ull n)
        {
            switch (n)
            {
            case 0: case 1:
                return false;
            case 2:
                return true;
            default:

                if (n % 2 == 0) return false;

                for (Ull i{3}; i * i <= n; i += 2)
                {
                    if (n % i == 0) return false;
                }
            }

            return true;
        }
    }
    using namespace mine;


    void Solve();

}

    //namespace 
    //{
    int main()
    {
        Solve();

        return 0;
    }
    //}

namespace
{
    void Solve()
    {
        int X, result{1};
        std::cin >> X;


        for (auto b : range(2, static_cast<int>(sqrt(X) + 1)))
        {
            for (int p{2}, exp; (exp = static_cast<int>(pow(b, p))) <= X; ++p)
            {
                if (X - exp == 0)
                {
                    std::cout << exp;
                    return;
                }
                if (X - exp < X - result) 
                {
                    result = exp;
                }
            }
        }

        std::cout << result;
        return;

    }
}

Measured memory_bytes: 640