#include <bits/stdc++.h>
using namespace std;
void build(long long v, long long tl, long long tr, long long st[],
           long long lz[], bool f[], long long a[]) {
  if (tl == tr) {
    st[v] = a[tl];
    lz[v] = 0LL;
    f[v] = false;
    return;
  }
  build((v << 1), tl, ((tl + tr) >> 1), st, lz, f, a);
  build((v << 1) | 1, ((tl + tr) >> 1) + 1, tr, st, lz, f, a);
  st[v] = st[(v << 1)] + st[(v << 1) | 1];
  lz[v] = 0LL;
  f[v] = false;
  return;
}
void push(long long v, long long tl, long long tr, long long st[],
          long long lz[], bool f[]) {
  if (f[v]) {
    st[(v << 1)] = lz[(v << 1)] = st[(v << 1) | 1] = lz[(v << 1) | 1] = 0LL;
    f[(v << 1)] = f[(v << 1) | 1] = true;
    f[v] = false;
  }
  st[(v << 1)] += lz[v] * (((tl + tr) >> 1) - tl + 1);
  lz[(v << 1)] += lz[v];
  st[(v << 1) | 1] += lz[v] * (tr - ((tl + tr) >> 1));
  lz[(v << 1) | 1] += lz[v];
  lz[v] = 0LL;
  return;
}
void update(long long v, long long tl, long long tr, long long l, long long r,
            long long val, bool set, long long st[], long long lz[], bool f[]) {
  if (l > r) {
    return;
  }
  if (l == tl && tr == r) {
    if (set) {
      st[v] = lz[v] = 0LL;
      f[v] = true;
    }
    st[v] += val * (tr - tl + 1);
    lz[v] += val;
    return;
  }
  push(v, tl, tr, st, lz, f);
  update((v << 1), tl, ((tl + tr) >> 1), l, min(r, ((tl + tr) >> 1)), val, set,
         st, lz, f);
  update((v << 1) | 1, ((tl + tr) >> 1) + 1, tr, max(l, ((tl + tr) >> 1) + 1),
         r, val, set, st, lz, f);
  st[v] = st[(v << 1)] + st[(v << 1) | 1];
  return;
}
long long query(long long v, long long tl, long long tr, long long l,
                long long r, long long st[], long long lz[], bool f[]) {
  if (l > r) {
    return 0LL;
  }
  if (l == tl && tr == r) {
    return st[v];
  }
  push(v, tl, tr, st, lz, f);
  return query((v << 1), tl, ((tl + tr) >> 1), l, min(r, ((tl + tr) >> 1)), st,
               lz, f) +
         query((v << 1) | 1, ((tl + tr) >> 1) + 1, tr,
               max(l, ((tl + tr) >> 1) + 1), r, st, lz, f);
}
void build(int v, int tl, int tr, int a[], long long st[]) {
  if (tl == tr) {
    st[v] = a[tl];
    return;
  }
  int tm = ((tl + tr) / 2);
  build(2 * v, tl, tm, a, st);
  build(2 * v + 1, tm + 1, tr, a, st);
  st[v] = st[v * 2] + st[v * 2 + 1];
  return;
}
void update(int v, int tl, int tr, int pos, int val, long long st[]) {
  if (tl == tr && tl == pos) {
    st[v] = val;
    return;
  }
  if (tl > pos || tr < pos) {
    return;
  }
  int tm = ((tl + tr) / 2);
  update(2 * v, tl, tm, pos, val, st);
  update(2 * v + 1, tm + 1, tr, pos, val, st);
  st[v] = st[v * 2] + st[v * 2 + 1];
  return;
}
long long query(int v, int tl, int tr, int l, int r, long long st[]) {
  if (tl == l && tr == r) {
    return st[v];
  }
  if (l > r) {
    return 0LL;
  }
  int tm = ((tl + tr) / 2);
  return query(v * 2, tl, tm, l, std::min(tm, r), st) +
         query(v * 2 + 1, tm + 1, tr, std::max(tm + 1, l), r, st);
}
long long fn(long long x, long long rn[]) {
  if (x == rn[x])
    return x;
  else
    return rn[x] = fn(rn[x], rn);
}
bool un(long long x, long long y, long long rn[], long long sz[]) {
  x = fn(x, rn);
  y = fn(y, rn);
  if (x == y) return false;
  if (sz[x] < sz[y]) swap(x, y);
  sz[x] += sz[y];
  rn[y] = x;
  return true;
}
long long power(long long k) {
  long long temp = 1;
  for (long long i = 0; i <= k - 1; i++) {
    temp = temp * 2;
  }
  return temp;
}
bool compare(const pair<long long, long long> &a,
             const pair<long long, long long> &b) {
  return a.second < b.second;
}
pair<int, int> mostFrequent(long long arr[], long long n) {
  unordered_map<long long, long long> hash;
  for (long long i = 0; i < n; i++) hash[arr[i]]++;
  long long max_count = 0, res = -1;
  for (auto i : hash) {
    if (max_count < i.second) {
      res = i.first;
      max_count = i.second;
    }
  }
  pair<long long, long long> temp;
  temp.first = res;
  temp.second = max_count;
  return temp;
}
long long div(long long n) {
  if (n % 2 == 0) return 2;
  for (long long i = 3; i * i <= n; i += 2) {
    if (n % i == 0) return i;
  }
  return n;
}
long long gcd(long long a, long long b) {
  if (!b) return a;
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return (a * b) / gcd(a, b); }
bool sec(const pair<long long, long long> &a,
         const pair<long long, long long> &b) {
  return (a.first > b.first);
}
bool sec1(const pair<long long, long long> &a,
          const pair<long long, long long> &b) {
  return (a.second > b.second);
}
long long msum(long long a[], long long size) {
  long long max_so_far = a[0];
  long long curr_max = a[0];
  for (long long i = 0; i < size; i++) {
    curr_max = max(a[i], curr_max + a[i]);
    max_so_far = max(max_so_far, curr_max);
  }
  return max_so_far;
}
long long dist(tuple<long long, long long, long long> a,
               tuple<long long, long long, long long> b) {
  return ((get<0>(a) - get<0>(b)) * (get<0>(a) - get<0>(b)) +
          (get<1>(a) - get<1>(b)) * (get<1>(a) - get<1>(b)) +
          (get<2>(a) - get<2>(b)) * (get<2>(a) - get<2>(b)));
}
bool inv(const pair<int, int> &a, const pair<int, int> &b) {
  return (a.first > b.first);
}
vector<long long> vec;
vector<long long> freq;
void fac(long long n) {
  int count = 0;
  while (!(n % 2)) {
    n /= 2;
    count++;
  }
  if (count) {
    vec.push_back(2);
    freq.push_back(count);
  }
  for (long long i = 3; i <= sqrt(n); i += 2) {
    count = 0;
    while (n % i == 0) {
      count++;
      n = n / i;
    }
    if (count) {
      vec.push_back(i);
      freq.push_back(count);
    }
  }
  if (n > 2) {
    vec.push_back(n);
    freq.push_back(1);
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n;
  cin >> n;
  long long temp = n;
  fac(temp);
  if (n == 1) {
    cout << 1;
    return 0;
  } else {
    if (vec.size() == 1) {
      cout << vec[0];
    } else {
      cout << 1;
    }
  }
}

### Prompt

Generate a CPP solution to 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 namespace std;
void build(long long v, long long tl, long long tr, long long st[],
           long long lz[], bool f[], long long a[]) {
  if (tl == tr) {
    st[v] = a[tl];
    lz[v] = 0LL;
    f[v] = false;
    return;
  }
  build((v << 1), tl, ((tl + tr) >> 1), st, lz, f, a);
  build((v << 1) | 1, ((tl + tr) >> 1) + 1, tr, st, lz, f, a);
  st[v] = st[(v << 1)] + st[(v << 1) | 1];
  lz[v] = 0LL;
  f[v] = false;
  return;
}
void push(long long v, long long tl, long long tr, long long st[],
          long long lz[], bool f[]) {
  if (f[v]) {
    st[(v << 1)] = lz[(v << 1)] = st[(v << 1) | 1] = lz[(v << 1) | 1] = 0LL;
    f[(v << 1)] = f[(v << 1) | 1] = true;
    f[v] = false;
  }
  st[(v << 1)] += lz[v] * (((tl + tr) >> 1) - tl + 1);
  lz[(v << 1)] += lz[v];
  st[(v << 1) | 1] += lz[v] * (tr - ((tl + tr) >> 1));
  lz[(v << 1) | 1] += lz[v];
  lz[v] = 0LL;
  return;
}
void update(long long v, long long tl, long long tr, long long l, long long r,
            long long val, bool set, long long st[], long long lz[], bool f[]) {
  if (l > r) {
    return;
  }
  if (l == tl && tr == r) {
    if (set) {
      st[v] = lz[v] = 0LL;
      f[v] = true;
    }
    st[v] += val * (tr - tl + 1);
    lz[v] += val;
    return;
  }
  push(v, tl, tr, st, lz, f);
  update((v << 1), tl, ((tl + tr) >> 1), l, min(r, ((tl + tr) >> 1)), val, set,
         st, lz, f);
  update((v << 1) | 1, ((tl + tr) >> 1) + 1, tr, max(l, ((tl + tr) >> 1) + 1),
         r, val, set, st, lz, f);
  st[v] = st[(v << 1)] + st[(v << 1) | 1];
  return;
}
long long query(long long v, long long tl, long long tr, long long l,
                long long r, long long st[], long long lz[], bool f[]) {
  if (l > r) {
    return 0LL;
  }
  if (l == tl && tr == r) {
    return st[v];
  }
  push(v, tl, tr, st, lz, f);
  return query((v << 1), tl, ((tl + tr) >> 1), l, min(r, ((tl + tr) >> 1)), st,
               lz, f) +
         query((v << 1) | 1, ((tl + tr) >> 1) + 1, tr,
               max(l, ((tl + tr) >> 1) + 1), r, st, lz, f);
}
void build(int v, int tl, int tr, int a[], long long st[]) {
  if (tl == tr) {
    st[v] = a[tl];
    return;
  }
  int tm = ((tl + tr) / 2);
  build(2 * v, tl, tm, a, st);
  build(2 * v + 1, tm + 1, tr, a, st);
  st[v] = st[v * 2] + st[v * 2 + 1];
  return;
}
void update(int v, int tl, int tr, int pos, int val, long long st[]) {
  if (tl == tr && tl == pos) {
    st[v] = val;
    return;
  }
  if (tl > pos || tr < pos) {
    return;
  }
  int tm = ((tl + tr) / 2);
  update(2 * v, tl, tm, pos, val, st);
  update(2 * v + 1, tm + 1, tr, pos, val, st);
  st[v] = st[v * 2] + st[v * 2 + 1];
  return;
}
long long query(int v, int tl, int tr, int l, int r, long long st[]) {
  if (tl == l && tr == r) {
    return st[v];
  }
  if (l > r) {
    return 0LL;
  }
  int tm = ((tl + tr) / 2);
  return query(v * 2, tl, tm, l, std::min(tm, r), st) +
         query(v * 2 + 1, tm + 1, tr, std::max(tm + 1, l), r, st);
}
long long fn(long long x, long long rn[]) {
  if (x == rn[x])
    return x;
  else
    return rn[x] = fn(rn[x], rn);
}
bool un(long long x, long long y, long long rn[], long long sz[]) {
  x = fn(x, rn);
  y = fn(y, rn);
  if (x == y) return false;
  if (sz[x] < sz[y]) swap(x, y);
  sz[x] += sz[y];
  rn[y] = x;
  return true;
}
long long power(long long k) {
  long long temp = 1;
  for (long long i = 0; i <= k - 1; i++) {
    temp = temp * 2;
  }
  return temp;
}
bool compare(const pair<long long, long long> &a,
             const pair<long long, long long> &b) {
  return a.second < b.second;
}
pair<int, int> mostFrequent(long long arr[], long long n) {
  unordered_map<long long, long long> hash;
  for (long long i = 0; i < n; i++) hash[arr[i]]++;
  long long max_count = 0, res = -1;
  for (auto i : hash) {
    if (max_count < i.second) {
      res = i.first;
      max_count = i.second;
    }
  }
  pair<long long, long long> temp;
  temp.first = res;
  temp.second = max_count;
  return temp;
}
long long div(long long n) {
  if (n % 2 == 0) return 2;
  for (long long i = 3; i * i <= n; i += 2) {
    if (n % i == 0) return i;
  }
  return n;
}
long long gcd(long long a, long long b) {
  if (!b) return a;
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return (a * b) / gcd(a, b); }
bool sec(const pair<long long, long long> &a,
         const pair<long long, long long> &b) {
  return (a.first > b.first);
}
bool sec1(const pair<long long, long long> &a,
          const pair<long long, long long> &b) {
  return (a.second > b.second);
}
long long msum(long long a[], long long size) {
  long long max_so_far = a[0];
  long long curr_max = a[0];
  for (long long i = 0; i < size; i++) {
    curr_max = max(a[i], curr_max + a[i]);
    max_so_far = max(max_so_far, curr_max);
  }
  return max_so_far;
}
long long dist(tuple<long long, long long, long long> a,
               tuple<long long, long long, long long> b) {
  return ((get<0>(a) - get<0>(b)) * (get<0>(a) - get<0>(b)) +
          (get<1>(a) - get<1>(b)) * (get<1>(a) - get<1>(b)) +
          (get<2>(a) - get<2>(b)) * (get<2>(a) - get<2>(b)));
}
bool inv(const pair<int, int> &a, const pair<int, int> &b) {
  return (a.first > b.first);
}
vector<long long> vec;
vector<long long> freq;
void fac(long long n) {
  int count = 0;
  while (!(n % 2)) {
    n /= 2;
    count++;
  }
  if (count) {
    vec.push_back(2);
    freq.push_back(count);
  }
  for (long long i = 3; i <= sqrt(n); i += 2) {
    count = 0;
    while (n % i == 0) {
      count++;
      n = n / i;
    }
    if (count) {
      vec.push_back(i);
      freq.push_back(count);
    }
  }
  if (n > 2) {
    vec.push_back(n);
    freq.push_back(1);
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n;
  cin >> n;
  long long temp = n;
  fac(temp);
  if (n == 1) {
    cout << 1;
    return 0;
  } else {
    if (vec.size() == 1) {
      cout << vec[0];
    } else {
      cout << 1;
    }
  }
}

```