세제곱수의 합

양의 정수 $n$이 주어진다.

$n$을 하나 이상의 양의 세제곱수의 합으로 나타내려고 한다. 즉, 다음을 만족하는 자연수 $k$와 자연수 $a_1, a_2, \dots, a_k$를 찾고자 한다.

이때 가능한 $k$의 최솟값을 구하여라.

첫째 줄에 양의 정수 $n$이 주어진다.

$n$을 양의 세제곱수들의 합으로 나타내기 위해 필요한 항의 개수의 최솟값을 출력한다.

$1 \le n \le 10^{10}$