버스 수

수학자 G.H. 하디와 스리니바사 라마누잔에 얽힌 유명한 일화가 있다. 하디의 말로는 다음과 같다.

병환으로 퍼트니에 누워 있던 라마누잔을 찾아갔을 때의 일이다. 나는 1729호 택시를 타고 갔는데, 그 수가 별로 재미없는 수 같다고, 좋지 않은 징조가 아니기를 바란다고 말했다. 그러자 라마누잔이 대답했다. "아니요, 아주 흥미로운 수입니다. 두 양의 세제곱수의 합으로 서로 다른 두 가지 방법으로 나타낼 수 있는 가장 작은 수입니다."

택시 수라는 이름은 이 일화에서 비롯되었다. $n$번째 택시 수는 두 양의 세제곱수의 합으로 $n$가지 서로 다른 방법으로 나타낼 수 있는 가장 작은 수로 정의한다.

택시 수는 상당히 빠르게 커지기 때문에 계산하기가 매우 어렵고, 그다지 재미있지도 않다. 이 개념을 변형하여 버스 수를 생각해 보자. 버스 수란 두 양의 세제곱수의 합으로 적어도 $2$가지 서로 다른 방법으로 나타낼 수 있는 모든 수이다. 이 정의에 따르면 첫 번째를 제외한 모든 택시 수도 버스 수이다.

여러분의 과제는 버스 수를 생성하는 프로그램을 작성하는 것이다. 구체적으로는 어떤 한계 $m$보다 크지 않은 버스 수 가운데 가장 큰 수를 구해야 한다.

입력은 다음과 같다.

• 버스 수의 상한 $m$ ($1 \le m \le 400\,000$)이 주어지는 한 줄.

$m$을 넘지 않는 가장 큰 버스 수 $x$를 출력한다. 그러한 수가 없으면 none을 출력한다.