题目描述

江桥 发现了一个字符串古木 $s$。现在，他打算用这个古木来爬雪山。 古木 $s$ 是一个长度为 $n$ 只包含小写字母的字符串。江桥 打算将 $s$ 划分为若干个相邻且不重叠的非空连续子串 $s_1,s_2,\dots,s_k$，且保持原来的顺序，使得 $s_1s_2\cdots s_k = s$。 在保证分割后的子串序列按字典序不下降的前提下（因为下降了就越爬越低了），最多可以将 $s$ 划分为多少段？

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

输入格式

每个测试文件均包含多组测试数据。第一行输入一个整数 $T$ 代表数据组数，每组测试数据描述如下：

第一行输入一个正整数 $n$，表示字符串$s$ 的长度。

第二行输入一个长度为 $n$，仅由小写字母构成的字符串$s$。

输出格式

对于每一组测试数据，新起一行输出一个正整数，表示能被划分的最多段数。

3
6
azaazz
4
ztda
7
abababa

3
1
4

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

样例解释

对于第一组测试数据，$\texttt{"azaazz"}$ 可以分割为 $\{\texttt{a}, \texttt{zaa}, \texttt{zz}\}$，分割后的字符串数组字典序不下降。

数据规模与约定

下发文件

下发文件对应子任务 $3,4,5$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq T \leq 10^3$$,1 \leq n,\sum n \leq 7 \times 10^3$。