$n$ 的数据范围是 $[1,1500]$。

我觉得 $n=1$ 的时候答案应该是 $1$ 吧，但好像大部分题解都没特判，样例也没有这个点。