Rescue Niwen!
Contest: Codeforces Round 741 (Div. 2)
Difficulty rating: 2500
Tags: dp, greedy, string suffix structures, strings

After crossing the Windswept Wastes, Ori has finally reached the Windtorn Ruins to find the Heart of the Forest! However, the ancient repository containing this priceless Willow light did not want to open!

Ori was taken aback, but the Voice of the Forest explained to him that the cunning Gorleks had decided to add protection to the repository.

The Gorleks were very fond of the "string expansion" operation. They were also very fond of increasing subsequences.

Suppose a string $$$s_1s_2s_3 \ldots s_n$$$ is given. Then its "expansion" is defined as the sequence of strings $$$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$$$. For example, the "expansion" the string 'abcd' will be the following sequence of strings: 'a', 'ab', 'abc', 'abcd', 'b', 'bc', 'bcd', 'c', 'cd', 'd'.

To open the ancient repository, Ori must find the size of the largest increasing subsequence of the "expansion" of the string $$$s$$$. Here, strings are compared lexicographically.

Help Ori with this task!

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

Input format:
Each test contains multiple test cases.

The first line contains one positive integer $$$t$$$ ($$$1 \le t \le 10^3$$$), denoting the number of test cases. Description of the test cases follows.

The first line of each test case contains one positive integer $$$n$$$ ($$$1 \le n \le 5000$$$) — length of the string.

The second line of each test case contains a non-empty string of length $$$n$$$, which consists of lowercase latin letters.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^4$$$.

Output format:
For every test case print one non-negative integer — the answer to the problem.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In first test case the "expansion" of the string is: 'a', 'ac', 'acb', 'acba', 'acbac', 'c', 'cb', 'cba', 'cbac', 'b', 'ba', 'bac', 'a', 'ac', 'c'. The answer can be, for example, 'a', 'ac', 'acb', 'acba', 'acbac', 'b', 'ba', 'bac', 'c'.

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

Example output:
9
17
12
29
14
3
9

Editorial:
The constraints on the problem were chosen so that solutions slower than $$$O(n^2 \cdot log(n))$$$ would not get AC, or would get with difficulty. The solution could be, for example, to sort all substrings by assigning numbers to them, and then find the largest increasing subsequence in the resulting array.
Let us describe the solution for $$$O(n^2)$$$. The most important thing required for the solution is to understand what the largest increasing subsequence should look like.
Let $$$s$$$ — a string, and $$$n$$$ — the length of the string $$$s$$$.
It can be shown that if the largest increasing subsequence has a substring [$$$l$$$ ... $$$r$$$], then it also has a substring [$$$l$$$ ... $$$n$$$]. I will not give a formal proof, I will only give the key idea. Let the increasing subsequence first have the string [$$$l_1$$$ ... $$$r_1$$$], and then the substring [$$$l_2$$$ ... $$$r_2$$$], with $$$r_1 \neq n$$$. It can be understood that if suffixes [$$$l_1$$$ ... $$$n$$$] and [$$$l_2$$$ ... $$$n$$$] have some common prefix, and it has already been included in the largest increasing subsequence, then we can «drop» the prefixes of the suffix [$$$l_1$$$ . . $$$n$$$], and instead of them write exactly the same suffix prefixes of [$$$l_2$$$ ... $$$n$$$], and the size of the increasing subsequence will not change, and the condition above will be satisfied. If, however, the suffixes [$$$l_1$$$ ... $$$n$$$] and [$$$l_2$$$ ... $$$n$$$] have no common prefix, then we could take the suffix itself [$$$l_2$$$ ... $$$n$$$] together with its prefixes, and the answer would only improve.
Thus, the largest increasing subsequence looks like this: first comes some substring [$$$l_1$$$ ... $$$r_1$$$], followed by a substring [$$$l_1$$$ ... $$$r_1 + 1$$$], and so on, ending with the suffix [$$$l_1$$$ ... $$$n$$$]. After that comes some substring [$$$l_2$$$ ... $$$r_2$$$], followed by a substring [$$$l_2$$$ ... $$$r_2 + 1$$$], and so on, ending with the suffix [$$$l_2$$$ ... $$$n$$$], and so on. Moreover, knowing which suffixes are included in this subsequence, we can establish all other substrings. Indeed, let the suffixes [$$$l_1$$$ ... $$$n$$$] and [$$$l_2$$$ ... $$$n$$$] be included in the sequence, and $$$l_1$$$ < $$$l_2$$$. Then it is not difficult to see that the suffix prefixes [$$$l_2$$$ ... $$$n$$$] can be typed greedily, namely, to take all substring [$$$l_2$$$ ... $$$k$$$] such that they are larger than the suffix [$$$l_1$$$ ... $$$n$$$].
Note that if the substring [$$$l_2$$$ ... $$$m$$$] is larger than the suffix [$$$l_1$$$ ... $$$n$$$], then the substring [$$$l_2$$$ ... $$$m+1$$$] is also larger than the suffix [$$$l_1$$$ ... $$$n$$$]. And so, we can use the following algorithm to find out $$$r_2$$$, that is, to find out which suffix prefix [$$$l_2$$$ ... $$$n$$$] to start typing the subsequence. Let $$$d_{l_1,l_2}$$$ — be the size of the largest common prefix of suffixes [$$$l_1$$$ ... $$$n$$$] and [$$$l_2$$$ ... $$$n$$$]. Then it is easy to see that if the suffix [$$$l_2$$$ ... $$$n$$$] is larger than the suffix [$$$l_1$$$ ... $$$n$$$], then the appropriate $$$r_2$$$ is $$$d_{l_1,l_2} + l_2$$$, which means that you must start typing all substrings, starting from the one that differs from the largest common prefix of the two suffixes.
So now we are left with two problems. The first is — you have to learn to quickly recognize the greatest common prefix of the two suffixes. The second is — to write a DP that would allow you to recognize the answer.
Let's see how to solve the first problem. You can use different string algorties, such as a suffix array. Or we can write a simple DP that calculates an array $$$d$$$ of the largest common prefixes over $$$O(n^2)$$$. The transitions in this DP and its implementation can be seen in the author's solution code (lines 37-48).
Now about the DP that calculates the answer. Let us use the facts above and do the following. Let $$$dp_i$$$ denote the size of the answer if the last substring in it is the suffix [$$$i$$$ ... $$$n$$$]. Let $$$dp_1 = n$$$, and then $$$dp_i = n - i + 1$$$. Now let's do the following. We will go through $$$i$$$ from $$$2$$$ to $$$n$$$, doing the following simple steps: for each $$$j$$$ from $$$1$$$ to $$$i-1$$$ ($$$j$$$ denotes the previous suffix in the answer) we will check how many substring of the suffix [$$$i$$$ ... $$$n$$$] we can take: if the suffix [$$$i$$$ ... $$$n$$$] is larger than the suffix [$$$j$$$ ... $$$n$$$], we calculate this number with the above described algorithm, using the $$$d$$$ array of largest common prefixes. Otherwise, we will not update, because the suffix [$$$i$$$ ... $$$n$$$] is less than or equal to the suffix [$$$j$$$ ... $$$n$$$], we cannot take it in response. It is not difficult to guess that the answer is maximal in all $$$dp_i$$$.
Thus, the problem is solved using two uncomplicated dynamics.
Asymptotics: $$$O(n^2)$$$ per test case.