CF1562E Rescue Niwen!

晨曦沙漠的太阳在地平线上升起，照耀着时光的沙粒…… —— Fates Warning，《Exodus》 穿越了风吹沙地后，Ori 终于到达了风裂遗迹，寻找森林之心！然而，封存着这无价柳树之光的古老仓库却不愿开启！ Ori 感到惊讶，但森林之声向他解释，狡猾的 Gorlek 族人为仓库加上了保护措施。 Gorlek 族人非常喜欢“字符串扩展”操作。他们也非常喜欢递增子序列。 假设给定一个字符串 $s_1s_2s_3\ldots s_n$。那么它的“扩展”定义为如下字符串序列：$s_1$，$s_1s_2$，…，$s_1s_2\ldots s_n$，$s_2$，$s_2s_3$，…，$s_2s_3\ldots s_n$，$s_3$，$s_3s_4$，…，$s_{n-1}s_n$，$s_n$。例如，字符串 'abcd' 的“扩展”序列为：'a'，'ab'，'abc'，'abcd'，'b'，'bc'，'bcd'，'c'，'cd'，'d'。 为了打开古老的仓库，Ori 必须找到字符串 $s$ 的“扩展”中，按字典序递增的最大子序列的长度。 请你帮助 Ori 完成这个任务！ 字符串 $a$ 在字典序上小于字符串 $b$ 当且仅当满足以下条件之一： - $a$ 是 $b$ 的前缀，且 $a \ne b$； - 在 $a$ 和 $b$ 第一个不同的位置，$a$ 的字母在字母表中排在 $b$ 的对应字母之前。

每个测试包含多个测试用例。 第一行包含一个正整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个正整数 $n$（$1 \le n \le 5000$），表示字符串的长度。 每个测试用例的第二行包含一个长度为 $n$ 的非空字符串，仅由小写拉丁字母组成。 保证所有测试用例中 $n$ 的总和不超过 $10^4$。

对于每个测试用例，输出一个非负整数，表示问题的答案。

在第一个测试用例中，字符串的“扩展”为：'a'，'ac'，'acb'，'acba'，'acbac'，'c'，'cb'，'cba'，'cbac'，'b'，'ba'，'bac'，'a'，'ac'，'c'。答案可以是，例如：'a'，'ac'，'acb'，'acba'，'acbac'，'b'，'ba'，'bac'，'c'。 由 ChatGPT 4.1 翻译