#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using pii = std::pair<int, int>;
template <typename T>
static inline T gcd(T a, T b) {
  a = std::abs(a);
  b = std::abs(b);
  while (b > 0) {
    a %= b;
    std::swap(a, b);
  }
  return a;
}
template <typename T>
static inline T sqr(T a) {
  return a * a;
}
template <typename T>
static inline bool remin(T &a, const T &val) {
  if (a > val) {
    a = val;
    return true;
  }
  return false;
}
template <typename T>
static inline bool remax(T &a, const T &val) {
  if (a < val) {
    a = val;
    return true;
  }
  return false;
}
static inline ll nxt() {
  int64_t first;
  scanf("%" PRId64, &first);
  return first;
}
static inline void skipEndLine() {
  char c = getchar();
  while (c != '\n') {
    c = getchar();
  }
}
static inline std::string nxtLine() {
  std::string ret;
  char c = '\n';
  while (true) {
    c = getchar();
    if (c == '\n' || c == '\r' || c == -1) {
      break;
    }
    ret.push_back(c);
  }
  return ret;
}
static inline std::string nxtString() {
  std::string ret;
  char c = '\n';
  while (true) {
    c = getchar();
    if (!isspace(c)) {
      break;
    }
  }
  if (c == -1) {
    return ret;
  }
  ret.push_back(c);
  while (true) {
    c = getchar();
    if (isspace(c) || c == -1) {
      break;
    }
    ret.push_back(c);
  }
  return ret;
}
static std::chrono::system_clock::time_point clock_t0;
static inline void init_time() { clock_t0 = std::chrono::system_clock::now(); }
static inline double get_time() {
  auto t = std::chrono::system_clock::now();
  return std::chrono::duration<double>((t - clock_t0)).count();
}
static inline void print_time(const std::string &name) {
  std::cerr << name << " " << get_time() << "s." << std::endl;
}
template <class T>
static inline T pw(T a, ll n) {
  T ret = T(1);
  while (n > 0) {
    if (n & 1) ret = ret * a;
    a = a * a;
    n >>= 1;
  }
  return ret;
}
static inline ll pw(ll a, ll n, ll m) {
  a %= m;
  ll ret = 1;
  while (n > 0) {
    if (n & 1) ret = ret * a % m;
    a = a * a % m;
    n >>= 1;
  }
  return ret;
}
class ThreadPool {
 public:
  ThreadPool(size_t);
  template <class F, class... Args>
  auto enqueue(F &&f, Args &&...args)
      -> std::future<typename std::result_of<F(Args...)>::type>;
  ~ThreadPool();

 private:
  std::vector<std::thread> workers;
  std::queue<std::function<void()> > tasks;
  std::mutex queue_mutex;
  std::condition_variable condition;
  bool stop;
};
inline ThreadPool::ThreadPool(size_t threads) : stop(false) {
  for (size_t i = 0; i < threads; ++i) {
    auto f = [this] {
      for (;;) {
        std::function<void()> task;
        {
          std::unique_lock<std::mutex> lock(this->queue_mutex);
          this->condition.wait(
              lock, [this] { return this->stop || !this->tasks.empty(); });
          if (this->stop && this->tasks.empty()) return;
          task = std::move(this->tasks.front());
          this->tasks.pop();
        }
        task();
      }
    };
    workers.emplace_back(f);
  }
}
template <class F, class... Args>
auto ThreadPool::enqueue(F &&f, Args &&...args)
    -> std::future<typename std::result_of<F(Args...)>::type> {
  using return_type = typename std::result_of<F(Args...)>::type;
  auto task = std::make_shared<std::packaged_task<return_type()> >(
      std::bind(std::forward<F>(f), std::forward<Args>(args)...));
  std::future<return_type> res = task->get_future();
  {
    std::unique_lock<std::mutex> lock(queue_mutex);
    if (stop) {
      throw std::runtime_error("enqueue on stopped ThreadPool");
    }
    tasks.emplace([task]() { (*task)(); });
  }
  condition.notify_one();
  return res;
}
inline ThreadPool::~ThreadPool() {
  {
    std::unique_lock<std::mutex> lock(queue_mutex);
    stop = true;
  }
  condition.notify_all();
  for (std::thread &worker : workers) {
    worker.join();
  }
}
static const ll ten9 = 1000 * 1000 * 1000;
template <class T>
struct Point2d {
  T first{0}, second{0};
  Point2d() = default;
  Point2d(T first, T second) : first(first), second(second) {}
  Point2d operator-(const Point2d &r) const {
    return Point2d(first - r.first, second - r.second);
  }
  Point2d operator+(const Point2d &r) const {
    return Point2d(first + r.first, second + r.second);
  }
  Point2d operator*(const T &r) const { return Point2d(first * r, second * r); }
  bool operator<(const Point2d &p) const {
    if (first != p.first) return first < p.first;
    return second < p.second;
  }
  bool operator<=(const Point2d &p) const {
    if (first != p.first) return first <= p.first;
    return second <= p.second;
  }
  bool operator==(const Point2d &p) const {
    return first == p.first && second == p.second;
  }
  bool operator!=(const Point2d &p) const {
    return first != p.first || second != p.second;
  }
  bool operator>(const Point2d &p) const {
    if (first != p.first) return first > p.first;
    return second > p.second;
  }
  bool operator>=(const Point2d &p) const {
    if (first != p.first) return first >= p.first;
    return second >= p.second;
  }
  T sqlen() const { return first * first + second * second; }
  ld len() const { return sqrtl(sqlen()); }
};
template <class T>
static inline T dot(const Point2d<T> &l, const Point2d<T> &r) {
  return l.first * r.first + l.second * r.second;
}
template <class T>
static inline T cross(const Point2d<T> &l, const Point2d<T> &r) {
  return l.first * r.second - l.second * r.first;
}
struct Fenwick {
  std::vector<int> t;
  inline void init(int n) { t.assign(n, 0); }
  inline void inc(int p, int val) {
    for (; p < t.size(); p |= (p + 1)) {
      t[p] += val;
    }
  }
  inline int sum(int r) {
    int result = 0;
    for (; r >= 0; r &= (r + 1), --r) {
      result += t[r];
    }
    return result;
  }
  inline int sum(int l, int r) { return sum(r) - sum(l - 1); }
  inline void clear() {
    for (int &v : t) {
      v = 0;
    }
  }
};
static const ld PI = acosl(-1.0);
static const ll mod = ten9 + 7;
using pt = Point2d<ll>;
static std::mt19937_64 generator{123123};
using namespace std;
using ptd = Point2d<ld>;
void prepare() {}
struct DSU {
  vector<int> p;
  vector<int> sz;
  void init(int n) {
    p.resize(n);
    sz.assign(n, 1);
    iota(p.begin(), p.end(), 0);
  }
  int get(int v) {
    if (p[v] == v) return v;
    return p[v] = get(p[v]);
  }
  bool unite(int a, int b) {
    a = get(a);
    b = get(b);
    if (a == b) return false;
    if (sz[a] < sz[b]) {
      swap(a, b);
    }
    p[b] = a;
    sz[a] += sz[b];
    return true;
  }
};
int solve(int n) {
  int ans = n;
  vector<int> divs;
  for (int i = 2; i < n; ++i) {
    if (n % i == 0) {
      divs.push_back(i);
    }
  }
  DSU dsu;
  dsu.init(n);
  for (int i = 0; i < n; ++i) {
    for (int d : divs) {
      for (int j = i; j < n; j += d) {
        if (dsu.unite(i, j)) {
          --ans;
        }
      }
    }
  }
  return ans;
}
void solve() {
  ll n = nxt();
  for (ll i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      ll first = n;
      while (first % i == 0) {
        first /= i;
      }
      if (first == 1) {
        cout << i << "\n";
      } else {
        cout << 1 << "\n";
      }
      return;
    }
  }
  cout << n << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  init_time();
  prepare();
  int t = 1;
  for (int i = 0; i < t; ++i) {
    solve();
  }
  print_time("Time:");
  return 0;
}

### Prompt

In CPP, your task is to solve the following problem:

Ujan has been lazy lately, but now has decided to bring his yard to good shape. First, he decided to paint the path from his house to the gate.

The path consists of n consecutive tiles, numbered from 1 to n. Ujan will paint each tile in some color. He will consider the path aesthetic if for any two different tiles with numbers i and j, such that |j - i| is a divisor of n greater than 1, they have the same color. Formally, the colors of two tiles with numbers i and j should be the same if |i-j| > 1 and n mod |i-j| = 0 (where x mod y is the remainder when dividing x by y).

Ujan wants to brighten up space. What is the maximum number of different colors that Ujan can use, so that the path is aesthetic?

Input

The first line of input contains a single integer n (1 ≤ n ≤ 10^{12}), the length of the path.

Output

Output a single integer, the maximum possible number of colors that the path can be painted in.

Examples

Input


4


Output


2


Input


5


Output


5

Note

In the first sample, two colors is the maximum number. Tiles 1 and 3 should have the same color since 4 mod |3-1| = 0. Also, tiles 2 and 4 should have the same color since 4 mod |4-2| = 0.

In the second sample, all five colors can be used.

<image>

### Response

```cpp
#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using pii = std::pair<int, int>;
template <typename T>
static inline T gcd(T a, T b) {
  a = std::abs(a);
  b = std::abs(b);
  while (b > 0) {
    a %= b;
    std::swap(a, b);
  }
  return a;
}
template <typename T>
static inline T sqr(T a) {
  return a * a;
}
template <typename T>
static inline bool remin(T &a, const T &val) {
  if (a > val) {
    a = val;
    return true;
  }
  return false;
}
template <typename T>
static inline bool remax(T &a, const T &val) {
  if (a < val) {
    a = val;
    return true;
  }
  return false;
}
static inline ll nxt() {
  int64_t first;
  scanf("%" PRId64, &first);
  return first;
}
static inline void skipEndLine() {
  char c = getchar();
  while (c != '\n') {
    c = getchar();
  }
}
static inline std::string nxtLine() {
  std::string ret;
  char c = '\n';
  while (true) {
    c = getchar();
    if (c == '\n' || c == '\r' || c == -1) {
      break;
    }
    ret.push_back(c);
  }
  return ret;
}
static inline std::string nxtString() {
  std::string ret;
  char c = '\n';
  while (true) {
    c = getchar();
    if (!isspace(c)) {
      break;
    }
  }
  if (c == -1) {
    return ret;
  }
  ret.push_back(c);
  while (true) {
    c = getchar();
    if (isspace(c) || c == -1) {
      break;
    }
    ret.push_back(c);
  }
  return ret;
}
static std::chrono::system_clock::time_point clock_t0;
static inline void init_time() { clock_t0 = std::chrono::system_clock::now(); }
static inline double get_time() {
  auto t = std::chrono::system_clock::now();
  return std::chrono::duration<double>((t - clock_t0)).count();
}
static inline void print_time(const std::string &name) {
  std::cerr << name << " " << get_time() << "s." << std::endl;
}
template <class T>
static inline T pw(T a, ll n) {
  T ret = T(1);
  while (n > 0) {
    if (n & 1) ret = ret * a;
    a = a * a;
    n >>= 1;
  }
  return ret;
}
static inline ll pw(ll a, ll n, ll m) {
  a %= m;
  ll ret = 1;
  while (n > 0) {
    if (n & 1) ret = ret * a % m;
    a = a * a % m;
    n >>= 1;
  }
  return ret;
}
class ThreadPool {
 public:
  ThreadPool(size_t);
  template <class F, class... Args>
  auto enqueue(F &&f, Args &&...args)
      -> std::future<typename std::result_of<F(Args...)>::type>;
  ~ThreadPool();

 private:
  std::vector<std::thread> workers;
  std::queue<std::function<void()> > tasks;
  std::mutex queue_mutex;
  std::condition_variable condition;
  bool stop;
};
inline ThreadPool::ThreadPool(size_t threads) : stop(false) {
  for (size_t i = 0; i < threads; ++i) {
    auto f = [this] {
      for (;;) {
        std::function<void()> task;
        {
          std::unique_lock<std::mutex> lock(this->queue_mutex);
          this->condition.wait(
              lock, [this] { return this->stop || !this->tasks.empty(); });
          if (this->stop && this->tasks.empty()) return;
          task = std::move(this->tasks.front());
          this->tasks.pop();
        }
        task();
      }
    };
    workers.emplace_back(f);
  }
}
template <class F, class... Args>
auto ThreadPool::enqueue(F &&f, Args &&...args)
    -> std::future<typename std::result_of<F(Args...)>::type> {
  using return_type = typename std::result_of<F(Args...)>::type;
  auto task = std::make_shared<std::packaged_task<return_type()> >(
      std::bind(std::forward<F>(f), std::forward<Args>(args)...));
  std::future<return_type> res = task->get_future();
  {
    std::unique_lock<std::mutex> lock(queue_mutex);
    if (stop) {
      throw std::runtime_error("enqueue on stopped ThreadPool");
    }
    tasks.emplace([task]() { (*task)(); });
  }
  condition.notify_one();
  return res;
}
inline ThreadPool::~ThreadPool() {
  {
    std::unique_lock<std::mutex> lock(queue_mutex);
    stop = true;
  }
  condition.notify_all();
  for (std::thread &worker : workers) {
    worker.join();
  }
}
static const ll ten9 = 1000 * 1000 * 1000;
template <class T>
struct Point2d {
  T first{0}, second{0};
  Point2d() = default;
  Point2d(T first, T second) : first(first), second(second) {}
  Point2d operator-(const Point2d &r) const {
    return Point2d(first - r.first, second - r.second);
  }
  Point2d operator+(const Point2d &r) const {
    return Point2d(first + r.first, second + r.second);
  }
  Point2d operator*(const T &r) const { return Point2d(first * r, second * r); }
  bool operator<(const Point2d &p) const {
    if (first != p.first) return first < p.first;
    return second < p.second;
  }
  bool operator<=(const Point2d &p) const {
    if (first != p.first) return first <= p.first;
    return second <= p.second;
  }
  bool operator==(const Point2d &p) const {
    return first == p.first && second == p.second;
  }
  bool operator!=(const Point2d &p) const {
    return first != p.first || second != p.second;
  }
  bool operator>(const Point2d &p) const {
    if (first != p.first) return first > p.first;
    return second > p.second;
  }
  bool operator>=(const Point2d &p) const {
    if (first != p.first) return first >= p.first;
    return second >= p.second;
  }
  T sqlen() const { return first * first + second * second; }
  ld len() const { return sqrtl(sqlen()); }
};
template <class T>
static inline T dot(const Point2d<T> &l, const Point2d<T> &r) {
  return l.first * r.first + l.second * r.second;
}
template <class T>
static inline T cross(const Point2d<T> &l, const Point2d<T> &r) {
  return l.first * r.second - l.second * r.first;
}
struct Fenwick {
  std::vector<int> t;
  inline void init(int n) { t.assign(n, 0); }
  inline void inc(int p, int val) {
    for (; p < t.size(); p |= (p + 1)) {
      t[p] += val;
    }
  }
  inline int sum(int r) {
    int result = 0;
    for (; r >= 0; r &= (r + 1), --r) {
      result += t[r];
    }
    return result;
  }
  inline int sum(int l, int r) { return sum(r) - sum(l - 1); }
  inline void clear() {
    for (int &v : t) {
      v = 0;
    }
  }
};
static const ld PI = acosl(-1.0);
static const ll mod = ten9 + 7;
using pt = Point2d<ll>;
static std::mt19937_64 generator{123123};
using namespace std;
using ptd = Point2d<ld>;
void prepare() {}
struct DSU {
  vector<int> p;
  vector<int> sz;
  void init(int n) {
    p.resize(n);
    sz.assign(n, 1);
    iota(p.begin(), p.end(), 0);
  }
  int get(int v) {
    if (p[v] == v) return v;
    return p[v] = get(p[v]);
  }
  bool unite(int a, int b) {
    a = get(a);
    b = get(b);
    if (a == b) return false;
    if (sz[a] < sz[b]) {
      swap(a, b);
    }
    p[b] = a;
    sz[a] += sz[b];
    return true;
  }
};
int solve(int n) {
  int ans = n;
  vector<int> divs;
  for (int i = 2; i < n; ++i) {
    if (n % i == 0) {
      divs.push_back(i);
    }
  }
  DSU dsu;
  dsu.init(n);
  for (int i = 0; i < n; ++i) {
    for (int d : divs) {
      for (int j = i; j < n; j += d) {
        if (dsu.unite(i, j)) {
          --ans;
        }
      }
    }
  }
  return ans;
}
void solve() {
  ll n = nxt();
  for (ll i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      ll first = n;
      while (first % i == 0) {
        first /= i;
      }
      if (first == 1) {
        cout << i << "\n";
      } else {
        cout << 1 << "\n";
      }
      return;
    }
  }
  cout << n << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  init_time();
  prepare();
  int t = 1;
  for (int i = 0; i < t; ++i) {
    solve();
  }
  print_time("Time:");
  return 0;
}

```