C. Dont Overkill
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Tomeh always boasts "Strings are my playground"

yet he never manages to solve the problems without resorting to overkill.

To prove that simplicity is the true mark of mastery: Given a string $$$s$$$, write a program that outputs the frequency count of the most frequent substring$$$^\dagger$$$ within $$$s$$$, without using tomeh's overkill power.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 1000$$$), the number of test cases.

Each test case consists of two lines: The first line of each test case contains a single integer $$$N$$$ ($$$1 \le N \le 10^5$$$), representing the length of the string. The second line of each test case contains a string $$$s$$$ of length $$$N$$$, consisting of lowercase English letters.

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

Output

Output a single integer representing the frequency count of the most frequent substring within $$$s$$$.

Example
Input
3
4
abab
6
cabbca
2
dd
Output
2
2
2
Note

$$$^\dagger$$$A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.