Squares

양의 정수를 서로 다른 양의 정수의 제곱들의 합으로 나타내는 것을 분해라고 한다. 예를 들어 30은 분해가 두 가지 있다. $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(30) = 4$, $k(378) = 12$, $k(380) = 10$이다.

정수 $x$에 대해, $y > x$이고 $k(y) < k(x)$인 정수 $y$가 존재하면 $x$를 overgrown이라고 한다. 위 예시에서 378은 overgrown이다.

주어진 $n$에 대해 $k(n)$과 1 이상 $n$ 이하의 overgrown 정수의 개수를 구하라.

첫 번째 줄에 정수 $n$이 하나 주어진다. ($1 \le n \le 10^{18}$) 배점의 45%에 해당하는 테스트는 $n \le 50\,000\,000$을 만족한다. 그중 배점의 30%에 해당하는 테스트는 $n \le 1\,000\,000$을 만족하고, 더 작은 배점 20%의 테스트는 $n \le 1000$을 만족한다.

공백으로 구분된 정수 두 개를 출력한다. 첫 번째는 $k(n)$이고, 두 번째는 1 이상 $n$ 이하의 overgrown 정수의 개수이다. $k(n) = \infty$이면 첫 번째 수 대신 마이너스 기호(-)를 출력한다.