#include <bits/stdc++.h>
long long fact[200001];
long long inf = 1e18;
long long z = 1e9 + 7;
long long gdp(long long a, long long b) { return (a - (a % b)); }
long long ld(long long a, long long b) {
  if (a < 0) return -1 * gdp(abs(a), b);
  if (a % b == 0) return a;
  return (a + (b - a % b));
}
long long gd(long long a, long long b) {
  if (a < 0) return (-1 * ld(abs(a), b));
  return (a - (a % b));
}
long long gcd(long long a, long long b) {
  if (b > a) return gcd(b, a);
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long e_gcd(long long a, long long b, long long &x, long long &y) {
  if (b > a) return e_gcd(b, a, y, x);
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long x1, y1;
  e_gcd(b, a % b, x1, y1);
  x = y1;
  y = (x1 - ((a / b) * y1));
  return e_gcd(b, a % b, x1, y1);
}
long long power(long long a, long long b, long long p) {
  if (b == 0) return 1;
  long long c = power(a, b / 2, p);
  if (b % 2 == 0)
    return ((c * c) % p);
  else
    return ((((c * c) % p) * a) % p);
}
long long inverse(long long a, long long n) { return power(a, n - 2, n); }
long long max(long long a, long long b) {
  if (a > b) return a;
  return b;
}
long long min(long long a, long long b) {
  if (a < b) return a;
  return b;
}
long long left(long long i) { return ((2 * i) + 1); }
long long right(long long i) { return ((2 * i) + 2); }
long long ncr(long long n, long long r) {
  if (n < r || (n < 0) || (r < 0)) return 0;
  return ((((fact[n] * inverse(fact[r], z)) % z) * inverse(fact[n - r], z)) %
          z);
}
void swap(long long &a, long long &b) {
  long long c = a;
  a = b;
  b = c;
  return;
}
long double pi = acos(-1);
long long pow(long long a, long long b) {
  if (b == 0) return 1;
  long long c = pow(a, b / 2);
  if (b % 2 == 0)
    return (c * c);
  else
    return ((c * c) * a);
}
using namespace std;
const int N = 2e5 + 7;
const int M = 1e6 + 7;
vector<int> adj[N];
bool cmp(long long a, long long b) { return a < b; }
map<long long, long long> m;
void primeFactors(long long n) {
  while (n % 2 == 0) {
    m[2]++;
    n = n / 2;
  }
  for (long long i = 3; i <= sqrt(n); i = i + 2) {
    while (n % i == 0) {
      m[i]++;
      n = n / i;
    }
  }
  if (n > 2) m[n]++;
}
void solve() {
  long long n;
  cin >> n;
  bool flag = true;
  primeFactors(n);
  if (m.size() > 1 || n == 1)
    cout << 1 << endl;
  else if (m.size() == 1) {
    for (auto x : m) {
      if (x.second > 0) cout << x.first << endl;
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long t;
  t = 1;
  while (t--) {
    solve();
  }
}

### Prompt

Please formulate 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>
long long fact[200001];
long long inf = 1e18;
long long z = 1e9 + 7;
long long gdp(long long a, long long b) { return (a - (a % b)); }
long long ld(long long a, long long b) {
  if (a < 0) return -1 * gdp(abs(a), b);
  if (a % b == 0) return a;
  return (a + (b - a % b));
}
long long gd(long long a, long long b) {
  if (a < 0) return (-1 * ld(abs(a), b));
  return (a - (a % b));
}
long long gcd(long long a, long long b) {
  if (b > a) return gcd(b, a);
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long e_gcd(long long a, long long b, long long &x, long long &y) {
  if (b > a) return e_gcd(b, a, y, x);
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long x1, y1;
  e_gcd(b, a % b, x1, y1);
  x = y1;
  y = (x1 - ((a / b) * y1));
  return e_gcd(b, a % b, x1, y1);
}
long long power(long long a, long long b, long long p) {
  if (b == 0) return 1;
  long long c = power(a, b / 2, p);
  if (b % 2 == 0)
    return ((c * c) % p);
  else
    return ((((c * c) % p) * a) % p);
}
long long inverse(long long a, long long n) { return power(a, n - 2, n); }
long long max(long long a, long long b) {
  if (a > b) return a;
  return b;
}
long long min(long long a, long long b) {
  if (a < b) return a;
  return b;
}
long long left(long long i) { return ((2 * i) + 1); }
long long right(long long i) { return ((2 * i) + 2); }
long long ncr(long long n, long long r) {
  if (n < r || (n < 0) || (r < 0)) return 0;
  return ((((fact[n] * inverse(fact[r], z)) % z) * inverse(fact[n - r], z)) %
          z);
}
void swap(long long &a, long long &b) {
  long long c = a;
  a = b;
  b = c;
  return;
}
long double pi = acos(-1);
long long pow(long long a, long long b) {
  if (b == 0) return 1;
  long long c = pow(a, b / 2);
  if (b % 2 == 0)
    return (c * c);
  else
    return ((c * c) * a);
}
using namespace std;
const int N = 2e5 + 7;
const int M = 1e6 + 7;
vector<int> adj[N];
bool cmp(long long a, long long b) { return a < b; }
map<long long, long long> m;
void primeFactors(long long n) {
  while (n % 2 == 0) {
    m[2]++;
    n = n / 2;
  }
  for (long long i = 3; i <= sqrt(n); i = i + 2) {
    while (n % i == 0) {
      m[i]++;
      n = n / i;
    }
  }
  if (n > 2) m[n]++;
}
void solve() {
  long long n;
  cin >> n;
  bool flag = true;
  primeFactors(n);
  if (m.size() > 1 || n == 1)
    cout << 1 << endl;
  else if (m.size() == 1) {
    for (auto x : m) {
      if (x.second > 0) cout << x.first << endl;
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long t;
  t = 1;
  while (t--) {
    solve();
  }
}

```