雪遁·逃生
题号：NC299643
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

【题目背景】
\hspace{15pt}长期的和平生活消磨了企鹅文明的警惕，加上 MuQ 缺乏应对危机的经验，在 Kendieer 接连不断的猛烈攻势下，企鹅文明最终还是沦陷了。
\hspace{15pt}MuQ 只能眼睁睁地看着自己的子民一个一个被 Kendieer 吞噬。它含泪逃离战场，发誓一定要找到反击的机会。
\hspace{15pt}企鹅文明之所以能延续至今，很大程度上得益于四周环绕的雪山，形成了一个天然的屏障。如今 MuQ 却被困在这座曾经守护它们的雪山前，无法翻越。
\hspace{15pt}就在绝望之际，MuQ 在雪山脚下发现了一段造型奇特的字符串古木。它意识到，只要能将这段木材合理分割，或许就能搭建出一条翻越雪山的路径……
\hspace{15pt}MuQ 发现了一个字符串古木 s。现在，他打算用这个古木来爬雪山。
\hspace{15pt}古木 s 是一个长度为 n 只包含小写字母的字符串。MuQ 打算将 s 划分为若干个相邻且不重叠的非空连续子串 s_1,s_2,\dots,s_k，且保持原来的顺序，使得 s_1s_2\cdots s_k = s。
\hspace{15pt}在保证分割后的子串序列按字典序不下降的前提下（因为下降了就越爬越低了），最多可以将 s 划分为多少段？

【名词解释】
\hspace{15pt}字符串的字典序比较：从左到右逐个比较两个字符串的字符。如果在某个位置上字符不同，比较这两个字符的字母表顺序，字母序大的字符串字典序也大。如果一直比较到其中一个字符串结束，则较短的字符串字典序更小。

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leq T\leq 10^3\right) 代表数据组数，每组测试数据描述如下：
\hspace{15pt}第一行输入一个正整数 n\left(1\leq n\leq2 \times 10^3\right)，表示字符串 s 的长度。
\hspace{15pt}第二行输入一个长度为 n，仅由小写字母构成的字符串 s。
\hspace{15pt}除此之外，保证单个测试文件的字符串长度之和不超过 2 \times 10^3。

输出描述:

\hspace{15pt}对于每一组测试数据，新起一行输出一个正整数，表示能被划分的最多段数。
示例1

输入

复制 
3
6
azaazz
4
ztda
7
abababa

输出

复制 
3
1
4

说明

\hspace{15pt}对于第一组测试数据，\texttt{ 可以分割为 \{\texttt{a}, \texttt{zaa}, \texttt{zz}\}，分割后的字符串数组字典序不下降。
示例2

输入

复制 
8
4
baka
10
newanderer
4
cute
4
papy
4
dumb
8
kendieer
6
hajimi
11
mlibfeather

输出

复制 
2
2
2
2
2
3
3
2

备注: