题目描述

给定一个正整数 $N$。找出不大于 $N$ 的最大回文立方数。这里，当且仅当一个正整数 $K$ 满足以下两个条件时，它被定义为回文立方数:

1. 存在一个正整数 $x$ 使得 $x^3 = K$。

2. K 的十进制表示(不含前导零)是一个回文数。更准确地说，如果用 $K = \sum_{i = 0}^{L-1} A_i10^i$ 表示 K，其中 $A_0, A_1, \ldots, A_{L-2}$ 是 0 到 9 之间的整数，$A_{L-1}$ 是 1 到 9 之间的整数，那么对于所有 $i = 0, 1, \ldots, L-1$，都有 $A_i = A_{L-1-i}$。

输入格式

输入$N$。

输出格式

输出所求答案。

样例

345

343

6

1

123456789012345

1334996994331

样例1解释

343 是一个回文立方数，而 344 和 345 不是。因此，答案是 343。

数据范围

$N$ 是不大于 $10^{18}$ 的正整数。

来源

• AtCoder ABC343C