rt，暴力 DP，$O(qn^3)$ 的时间复杂度，$q,n \le 500$，显然无法通过的时间复杂度跑得飞快，最慢也就 $864\ \text{ms}$，还没有卡常，建议加强数据。

记录。

$n$ 是字符串的长度。