You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小明和小红在玩一个无聊的游戏，名字叫“选数”。

具体的：小明从$1,...,n$中选一个数$x$，小红从$1,...,n$中选一个数$y$。

要求是：$x<y$，$x$与$y$互质，且，$x$含有的质因子种类数加上$y$含有的质因子种类数最多。

质因子的种类数的意思是，含有几种不同的质因子。
比如12=2*2*3
那么12含有2种不同的质因子。

问：小明和小红有多少种选择数字的方案。

输入格式

第一行输入$n$。

输出格式

两个整数，第一个整数代表$x,y$质因子种类数最多能有多少，第二个整数代表方案数。

10

3 5 

样例解释 #1

以下是$5$种合法的方案，都含有$3$种不同的质因子。

6 5，6 7，3 10，9 10，7 10

30

4 15

55

5 1

样例解释 #3

唯一合法的方案是42 55。

11451

8 7925

数据范围

测试点1-6：$n\leq 1000$。

测试点7：$n\leq 10^4$。

测试点8：$n\leq 10^5$。

测试点9：$n\leq 10^6$。

测试点10：$n\leq 10^7$。

测试点11-12：$n\leq 10^8$。

测试点13-14：$n\leq 10^9$。

测试点15-16：$n\leq 10^{10}$。

测试点17-18：$n\leq 10^{11}$。

对于100%的数据：$n\leq 10^{12}$。