C: 約数ゲーム / Divisor Game

問題

tsutaj くんは約数ゲームで遊ぼうとしています。

約数ゲームでは、まず 2 以上の自然数 N が与えられ、その後は以下の手順でゲームが進んでいきます。

• N 以外の N の約数の中から、整数を 1 つ宣言する。ただしこのとき、既に宣言したことがある整数の約数になるものは宣言できない。
• 宣言できる整数がある限りこれを繰り返し、宣言できるものがなければゲームは終了する。

ゲームを終了させるまでに行われた宣言の回数としてあり得る数の最小値と最大値を求めてください。

入力形式

入力は 1 行で与えられる。

N

制約

• 2 \leq N \leq 10^{12}

出力形式

宣言回数の最小値と最大値を、スペース区切りで 1 行に出力せよ。

入力例1

18

出力例1

2 5

宣言回数を 2 回にする一例は以下の通りです。

• 9 を宣言する。
• 6 を宣言する。 (6 は 9 の約数ではないため宣言が可能である)

これを行うと、18 の約数で 18 でない任意の整数は今まで宣言してきた整数の約数になるため、ゲームが終了します。

既に宣言したことがある整数の約数になるものは宣言できないことに注意してください。例えば、 9 を宣言したあとに 3 を宣言することはできません。なぜなら、3 は 9 の約数になるからです。

入力例2

99

出力例2

2 5

入力例3

10000000019

出力例3

1 1

入力は 32 bit 整数型に収まらない場合があります。

Note

Link

 

---