题目背景

XJ 作为一所有悠久历史的名校，将迎来 70 周年校庆。

题目描述

这是 XJ 成立的第 $n$ 年的校庆。为了充分展现这次校庆的隆重，校长决定把它凑得尽量整。

现在，校长想知道，这次校庆在几进制下能使得其后缀 $0$ 尽量多。他决定把这一伟大的任务交给你完成。

输入格式

一行一个不为 $1$ 的十进制正整数 $n$。

输出格式

一个不为 $1$ 的正整数 $a$、一个正整数 $b$，用一个空格隔开，表示在 $a$ 进制下的 $n$ 后缀 $0$ 最多，可以表示成有 $b$ 个后缀 $0$ 的形式。
如有多个解，输出 $a$ 最大的。

样例

Input 1

14

Output 1

14 1

Input 2

1080

Output 2

6 3

Input 3

8796093022208

Output 3

2 43

Input 4

6750015597009009867

Output 4

1500001733 2

数据范围

• 对于 $10\%$ 的数据，$n$ 为质数。
• 对于 $30\%$ 的数据，$n = a^b$，其中 $a$ 为质数。
• 对于另外 $30\%$ 的数据，$n \leq 2 \times 10^{15}$。
• 对于 $100\%$ 的数据，$2 \leq n \leq 2^{63}-1$。

样例解释

• 对于样例 1：$(14)_{10} = (10)_{14}$，在 $14$ 进制下可表示成 $1$ 个后缀 $0$ 的形式，且 $14$ 是满足条件中最大的 $a$。虽然 $2$ 进制、$7$ 进制下也有 $1$ 个后缀 $0$，但输出 $a$ 最大的，因此答案为 14 1。
• 对于样例 2：$(1080)_{10} = (5000)_{6}$，在 $6$ 进制下有 $3$ 个后缀 $0$。
• 对于样例 3：$8796093022208 = 2^{43}$，在 $2$ 进制下有 $43$ 个后缀 $0$。
• 对于样例 4：$6750015597009009867 = 1500001733^2 \times 3$，在 $1500001733$ 进制下有 $2$ 个后缀 $0$。