Maximum Sequence Length of Identical Pets

You are given a series of test cases. In each test case, there are N cages arranged in a row, where each cage contains a pet represented by a lowercase letter. You are also given M sections; each section is described by two integers (L) and (R) (with (1 \le L \le R \le N)) representing the start and end positions (inclusive) of a segment of cages. Within each section, you are allowed to arbitrarily swap the pets. This means that, for each section, you can rearrange the pets in any order. Your goal is to determine the maximum possible contiguous sequence length of identical pet types that can be achieved by rearranging the pets within the specified sections. Essentially, for each test case, compute the maximum frequency of any pet type appearing in the union of the given sections.

For example, consider a test case where N = 6, the string is "abacca", M = 2, and the sections are [1, 3] and [4, 6]. In the first section, the pet counts are: a=2, b=1. In the second section, they are: c=2, a=1. When combined, the maximum frequency is 3 (for pet 'a').

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains a single integer (T) denoting the number of test cases.

For each test case:

• The first line contains an integer (N), the number of cages.
• The second line contains a string (P) of length (N), representing the pet type in each cage.
• The third line contains an integer (M), the number of sections.
• The next (M) lines each contain two integers (L) and (R), representing the start and end indices of a section (1-indexed).

It is guaranteed that (1 \le L \le R \le N).

outputFormat

For each test case, output a single integer on a new line — the maximum contiguous sequence length of the same pet type that can be achieved after rearranging the pets in the given sections.## sample

2
6
abacca
2
1 3
4 6
5
abcab
3
1 2
3 3
4 5

3
2