Uptown is hosting their annual Downside-Up dance, where they invite their antipodal neighbors from Downside to participate in a celebration of Up-Down harmony. The dance commences as follows:
The Uptownites and the Downsiders line up in a row in some order. Next, a consecutive segment of people is chosen to participate in the dance. In the spirit of intermingling, each person must be able to pair up with someone from the other city. That is to say, the segment chosen must contain the same number of Uptownites and Downsiders.
The dance organizers want this year's dance to be as big as possible. Given the orders that the Uptownites and Downsiders have lined up in, can you help them determine the longest segment of people they can choose to participate in the dance for each one?
The first line of the input contains a single integer $$$t$$$ $$$(1\leq t\leq 10^4)$$$ — the number of test cases. This is followed by the descriptions of the test cases.
The first line of each test case contains an integer $$$n$$$ $$$(1\leq n\leq 2\cdot 10^5)$$$, the number of people that are lined up.
The second line of each test case contains a string of length $$$n$$$ consisting of the characters U and D, denoting the city each person belongs to, with U representing an Uptownite and D representing a Downsider.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.
For each test case, output a single integer — the length of the longest consecutive segment containing the same number of Uptownites and Downsiders that can be chosen from the given ordering.
44UDUD7UUUDDDD10DDUDDUDUUD2DD
4 6 8 0
In the first test case, we can take all the people. Uptownites and Downsiders rejoice!
In the second test case, we can take the segment spanning from the first person to the sixth person.
In the third test case, we can take the segment spanning from the second person to the ninth person.
In the fourth test case, there are no Uptownites, so we cannot choose a segment of positive length at all.
