#include <bits/stdc++.h>
using namespace std;
const long long NUM = 1000000009;
const long long NUM2 = 998244353;
long long binpow(long long a, long long b) {
  if (b == 0) return 1;
  long long res = binpow(a, b / 2) % NUM;
  if (b % 2)
    return (((res * res) % NUM) * a) % NUM;
  else
    return (res * res) % NUM;
}
template <size_t sz>
struct bitset_comparer {
  bool operator()(const bitset<sz> &b1, const bitset<sz> &b2) const {
    return b1.to_ulong() < b2.to_ulong();
  }
};
struct hash_pair {
  template <class T1, class T2>
  size_t operator()(const pair<T1, T2> &p) const {
    auto hash1 = hash<T1>{}(p.first);
    auto hash2 = hash<T2>{}(p.second);
    return hash1 ^ hash2;
  }
};
long long fact(long long n);
long long nCr(long long n, long long r) {
  return fact(n) / (fact(r) * fact(n - r));
}
long long fact(long long n) {
  long long res = 1;
  for (long long i = 2; i <= n; i++) res = (res * i) % NUM;
  return (res) % NUM;
}
bool isPrime(long long n) {
  if (n == 1) return false;
  if (n == 2) return true;
  for (long long i = 2; i * i <= n; i++)
    if (n % i == 0) return false;
  return true;
}
long long ceil(long long a, long long b) {
  if (a % b == 0) {
    return a / b;
  } else {
    return (a / b) + 1;
  }
}
long long min(long long a, long long b) {
  if (a > b) {
    return b;
  }
  return a;
}
long long max(long long a, long long b) {
  if (a > b) return a;
  return b;
}
long long dif(long long a, long long b) {
  if (a > b) return a - b;
  return b - a;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) {
  long long k = gcd(a, b);
  return (a * b) / k;
}
void read(long long arr[], long long n) {
  for (long long i = 0; i < n; i++) {
    cin >> arr[i];
  }
}
void addedge(vector<vector<long long>> &v, long long p1, long long p2) {
  v[p1].push_back({p2});
  v[p2].push_back({p1});
}
bool mycmp(pair<long long, float> p1, pair<long long, float> p2) {
  return p1.first < p2.first;
}
void print(long long arr[], long long n) {
  for (long long i = 0; i < n; ++i) {
    cout << arr[i] << " ";
  }
  cout << endl;
}
bool mycmp2(pair<int, pair<int, int>> &p1, pair<int, pair<int, int>> &p2) {
  if (p1.second.first == p2.second.first) {
    return p1.first > p2.first;
  } else {
    return p1.second.first < p2.second.first;
  }
}
vector<int> prime;
void sieveOferatosthenes(int MAX) {
  bool pri[MAX + 1];
  memset(pri, true, sizeof(pri));
  pri[1] = false;
  for (int p = 2; p * p <= MAX; p++) {
    if (pri[p] == true) {
      for (int i = p * 2; i <= MAX; i += p) pri[i] = false;
    }
  }
  for (int i = 1; i <= MAX; i++) {
    if (pri[i]) {
      prime.push_back(i);
    }
  }
}
bool check(vector<pair<int, int>> &v) {
  for (auto it : v) {
    if (it.second != 1) {
      return true;
    }
  }
  return false;
}
void solve() {
  long long n;
  cin >> n;
  vector<pair<int, int>> v;
  long long k = n;
  long long res = 1;
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      res *= i;
      int num = 0;
      for (; n % i == 0; n /= i) {
        num++;
      }
      v.push_back({i, num});
    }
  }
  if (n > 1) {
    res *= n;
    v.push_back({n, 1});
  }
  n = k;
  long long ans = 0;
  int num = 0;
  for (int i = 0; i < v.size(); i++) {
    int j = 0;
    for (j = 0; binpow(2, j) < v[i].second; j++) {
    }
    num = max(num, j);
  }
  for (auto it : v) {
    if (it.second != binpow(2, num)) {
      cout << res << " " << num + 1 << endl;
      return;
    }
  }
  cout << res << " " << num << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  t = 1;
  while (t--) {
    solve();
  }
  return 0;
}

### Prompt

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

JATC's math teacher always gives the class some interesting math problems so that they don't get bored. Today the problem is as follows. Given an integer n, you can perform the following operations zero or more times:

  * mul x: multiplies n by x (where x is an arbitrary positive integer). 
  * sqrt: replaces n with √{n} (to apply this operation, √{n} must be an integer). 



You can perform these operations as many times as you like. What is the minimum value of n, that can be achieved and what is the minimum number of operations, to achieve that minimum value?

Apparently, no one in the class knows the answer to this problem, maybe you can help them?

Input

The only line of the input contains a single integer n (1 ≤ n ≤ 10^6) — the initial number.

Output

Print two integers: the minimum integer n that can be achieved using the described operations and the minimum number of operations required.

Examples

Input

20


Output

10 2

Input

5184


Output

6 4

Note

In the first example, you can apply the operation mul 5 to get 100 and then sqrt to get 10.

In the second example, you can first apply sqrt to get 72, then mul 18 to get 1296 and finally two more sqrt and you get 6.

Note, that even if the initial value of n is less or equal 10^6, it can still become greater than 10^6 after applying one or more operations.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long NUM = 1000000009;
const long long NUM2 = 998244353;
long long binpow(long long a, long long b) {
  if (b == 0) return 1;
  long long res = binpow(a, b / 2) % NUM;
  if (b % 2)
    return (((res * res) % NUM) * a) % NUM;
  else
    return (res * res) % NUM;
}
template <size_t sz>
struct bitset_comparer {
  bool operator()(const bitset<sz> &b1, const bitset<sz> &b2) const {
    return b1.to_ulong() < b2.to_ulong();
  }
};
struct hash_pair {
  template <class T1, class T2>
  size_t operator()(const pair<T1, T2> &p) const {
    auto hash1 = hash<T1>{}(p.first);
    auto hash2 = hash<T2>{}(p.second);
    return hash1 ^ hash2;
  }
};
long long fact(long long n);
long long nCr(long long n, long long r) {
  return fact(n) / (fact(r) * fact(n - r));
}
long long fact(long long n) {
  long long res = 1;
  for (long long i = 2; i <= n; i++) res = (res * i) % NUM;
  return (res) % NUM;
}
bool isPrime(long long n) {
  if (n == 1) return false;
  if (n == 2) return true;
  for (long long i = 2; i * i <= n; i++)
    if (n % i == 0) return false;
  return true;
}
long long ceil(long long a, long long b) {
  if (a % b == 0) {
    return a / b;
  } else {
    return (a / b) + 1;
  }
}
long long min(long long a, long long b) {
  if (a > b) {
    return b;
  }
  return a;
}
long long max(long long a, long long b) {
  if (a > b) return a;
  return b;
}
long long dif(long long a, long long b) {
  if (a > b) return a - b;
  return b - a;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) {
  long long k = gcd(a, b);
  return (a * b) / k;
}
void read(long long arr[], long long n) {
  for (long long i = 0; i < n; i++) {
    cin >> arr[i];
  }
}
void addedge(vector<vector<long long>> &v, long long p1, long long p2) {
  v[p1].push_back({p2});
  v[p2].push_back({p1});
}
bool mycmp(pair<long long, float> p1, pair<long long, float> p2) {
  return p1.first < p2.first;
}
void print(long long arr[], long long n) {
  for (long long i = 0; i < n; ++i) {
    cout << arr[i] << " ";
  }
  cout << endl;
}
bool mycmp2(pair<int, pair<int, int>> &p1, pair<int, pair<int, int>> &p2) {
  if (p1.second.first == p2.second.first) {
    return p1.first > p2.first;
  } else {
    return p1.second.first < p2.second.first;
  }
}
vector<int> prime;
void sieveOferatosthenes(int MAX) {
  bool pri[MAX + 1];
  memset(pri, true, sizeof(pri));
  pri[1] = false;
  for (int p = 2; p * p <= MAX; p++) {
    if (pri[p] == true) {
      for (int i = p * 2; i <= MAX; i += p) pri[i] = false;
    }
  }
  for (int i = 1; i <= MAX; i++) {
    if (pri[i]) {
      prime.push_back(i);
    }
  }
}
bool check(vector<pair<int, int>> &v) {
  for (auto it : v) {
    if (it.second != 1) {
      return true;
    }
  }
  return false;
}
void solve() {
  long long n;
  cin >> n;
  vector<pair<int, int>> v;
  long long k = n;
  long long res = 1;
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      res *= i;
      int num = 0;
      for (; n % i == 0; n /= i) {
        num++;
      }
      v.push_back({i, num});
    }
  }
  if (n > 1) {
    res *= n;
    v.push_back({n, 1});
  }
  n = k;
  long long ans = 0;
  int num = 0;
  for (int i = 0; i < v.size(); i++) {
    int j = 0;
    for (j = 0; binpow(2, j) < v[i].second; j++) {
    }
    num = max(num, j);
  }
  for (auto it : v) {
    if (it.second != binpow(2, num)) {
      cout << res << " " << num + 1 << endl;
      return;
    }
  }
  cout << res << " " << num << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  t = 1;
  while (t--) {
    solve();
  }
  return 0;
}

```