Description

Consider expressing a positive integer $n$ as a sum of several distinct squares. For example, $30 = 1^2 + 2^2 + 5^2 = 1^2 + 2^2 + 3^2 + 4^2$, while $8$ has no such decomposition.

Let $k(n)$ denote the minimal possible value of the largest base among all such decompositions of $n$. If no such decomposition exists, set $k(n) = \infty$. For example: $k(1) = 1$, $k(8) = \infty$, $k(378) = 12$, $k(380) = 10$.

A number $x$ is called "overweight" if and only if there exists $y > x$ such that $k(y) < k(x)$. From the examples above, $378$ is an "overweight" number.

Given $n$, you need to:

1. Compute $k(n)$.
2. Count how many "overweight" numbers are in the range from $1$ to $n$.

Input Format

The input contains a single line with a positive integer $n$.

Output Format

Output one line containing two integers, which are the answers to the two questions above. If $k(n) = \infty$, output a minus sign - instead.

30

4 15

Hint

Constraints

For 100 % of the testdata, $1 \le n \le 10^{18}$.

Original title: Kwadraty.

Translated by ChatGPT 5