← 返回题目列表

Codeforces · 1562/E

E. 救救尼文!

中文机器翻译题面 查看原题

穿过风吹荒原后,奥日终于到达风破废墟寻找森林之心!然而,蕴藏着这无价柳光的远古宝库并不想打开!

奥里大吃一惊,但森林之声向他解释说,狡猾的戈尔莱克斯决定对储存库增加保护。

Gorleks 非常喜欢“字符串扩展”操作。他们也非常喜欢增加子序列。

假设给出一个字符串 $$$s_1s_2s_3 \ldots s_n$$$。然后它的“扩展”被定义为字符串序列 $$$s_1$$$, $$$s_1 s_2$$$, ..., $$$s_1 s_2 \ldots s_n$$$, $$$s_2$$$, $$$s_2 s_3$$$, ..., $$$s_2 s_3 \ldots s_n$$$, $$$s_3$$$、$$$s_3 s_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$$$。

输出

对于每个测试用例,打印一个非负整数 - 问题的答案。

示例

输入 #1

7
5
acbac
8
acabacba
12
aaaaaaaaaaaa
10
abacabadac
8
dcbaabcd
3
cba
6
sparky

输出 #1

9
17
12
29
14
3
9

注意

在第一个测试用例中,字符串的“扩展”为:'a'、'ac'、'acb'、'acba'、'acbac'、'c'、'cb'、'cba'、'cbac'、'b'、'ba'、'bac'、'a'、'ac'、'c'。例如,答案可以是“a”、“ac”、“acb”、“acba”、“acbac”、“b”、“ba”、“bac”、“c”。