题目描述

考虑将正整数 $n$ 拆分成几个不同的平方数之和，比如 $30 = 1^2 + 2^2 + 5^2 = 1^2 + 2^2 + 3^2 + 4^2$，而 $8$ 不存在这样的拆分。

用 $k(n)$ 表示 $n$ 的拆分中，最大的底数最小可能是多少。如果 $n$ 不存在这样的拆分，则令 $k(n) = \infty$。例如：$k(1) = 1$，$k(8) = \infty$，$k(378) = 12$，$k(380) = 10$。

定义一个数 $x$ 被称为“超重”的，当且仅当存在 $y > x$，使得 $k(y) < k(x)$。从上面的例子可知，$378$ 是一个“超重”的数。

给定 $n$，你需要：

1. 求出 $k(n)$。
2. 求出 $1 \sim n$ 中有几个“超重”的数。

输入格式

输入仅一行，包含一个正整数 $n$。

输出格式

输出一行包含两个整数，分别为对上述两个问题的答案。如果 $k(n) = \infty$，则输出一个减号 - 代替。

30

4 15

提示

【数据范围】

对于 $100 \%$ 的数据，$1 \le n \le {10}^{18}$。

原题名称：Kwadraty。