题目描述

在遥远的魔法王国里，住着两位年轻的魔法师小珅和小泽。他们刚刚继承了王国的魔法宝座，为了证明自己的实力，他们决定进行一项神奇的仪式。

小珅和小泽在王宫的大厅里排列了 $n$ 颗魔法宝石，这些宝石最初都是黑色的，代表着王国的各个地区。他们要用自己的魔法逐步点亮这些宝石，让它们变成白色，象征着将魔法之光带到王国的每个角落。

仪式规则如下：

• 第 $1$ 天：小珅和小泽用魔法点亮第 $1$ 颗宝石。
• 第 $2$ 天：他们点亮所有序号是 $2$ 的倍数的宝石。
• 第 $3$ 天：他们点亮所有序号是 $3$ 的倍数的宝石。
• 第 $4$ 天：他们点亮所有序号是 $4$ 的倍数的宝石。
• 以此类推，第 $k$ 天他们会点亮所有序号是 $k$ 的倍数的宝石。

王国的智者们很好奇：

• 小珅和小泽最少需要多少天才能点亮所有的宝石？
• 最后一颗宝石（第 $n$ 颗）会在第几天被点亮？

输入格式

一个整数 $n$，表示魔法宝石的数量。

输出格式

输出两个整数，第一个整数表示点亮所有宝石所需要的最少天数，第二个整数表示第 $n$ 颗宝石被点亮的天数。

10

7 2

5236

5233 2

9999991

9999991 9999991

说明提示

对于样例 $1$，$n=10$：

• 第 $1$ 天：点亮第 $1$ 颗宝石。
• 第 $2$ 天：点亮第 $2,4,6,8,10$ 颗宝石。
• 第 $3$ 天：点亮第 $3,9$ 颗宝石（第 $6$ 颗已经被点亮）。
• 第 $4$ 天：没有新的宝石被点亮（第 $4,8$ 颗已经被点亮）。
• 第 $5$ 天：点亮第 $5$ 颗宝石（第 $10$ 颗已经被点亮）。
• 第 $6$ 天：没有新的宝石被点亮。
• 第 $7$ 天：点亮第 $7$ 颗宝石。

因此第 $7$ 天所有宝石都被点亮，第 $10$ 颗宝石在第 $2$ 天被点亮。

数据范围

• 对于 $10\%$ 的数据，$n=1$；
• 对于 $80\%$ 的数据，$1\le n\le 10^4$；
• 对于 $90\%$ 的数据，$1\le n\le 10^6$；
• 对于 $100\%$ 的数据，$1\le n\le 10^8$。

1

1 1

2

2 2