#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/14/problems/B

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████

Queue Fronts - Repovive Standard Round 5 | Repovive | Repovive

14B. Queue Fronts

1000 pts2s256 MB

There are $n$ people standing in $m$ queues. Each person has type A or type B.

The queues are numbered from $1$ to $m$ . In each queue, people have an order from the front to the back.

You may perform the following operations any number of times, in any order:

If $i > 1$ and queue $i$ is not empty, take the person at the front of queue $i$ and move them to the back of queue $i-1$ .
If $i < m$ and queue $i$ is not empty, take the person at the back of queue $i$ and move them to the front of queue $i+1$ .

For a non-empty queue, define its score as the length of the longest prefix of the queue whose people all have the same type. In other words, it is the number of consecutive people at the front of the queue with the same type as the front person.

The score of an empty queue is $0$ .

Your task is to maximize the sum of scores of all queues after performing any number of operations.

Constraints

$1 \le t \le 10^4$
$1 \le m \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 10^5$
The sum of $m$ over all test cases is at most $2 \times 10^5$
Each initial queue is non-empty.
The total number of characters in the $m$ given strings of a test case is exactly $n$ .
Each string consists only of characters A and B.

Input

t

\left. \begin{array}{l} n \quad m \\ s_1 \\ s_2 \\ \vdots \\ s_m \end{array} \right\} \times t

For each test case, $s_i$ describes the initial state of queue $i$ from front to back.

Output

\left. \begin{array}{l} \mathrm{ans} \end{array} \right\} \times t

For each test case, output the maximum possible sum of scores of all queues.

Samples

Input

Case 1

5 2
AA
BBA

Case 2

4 3
A
AA
A

Case 3

6 3
A
BA
BAB

Case 4

8 4
AB
BBB
AA
B

Case 5

10 3
BBA
AABBA
AB

Explanation

Case 1

Keeping the queues unchanged gives scores $2$ and $2$ , so the sum is $4$ . No arrangement with two queues can make the total score equal to $5$ .

Case 2

All people have type A, so all $4$ people can be counted in the front blocks of the queues.

Case 3

Every two adjacent people in the global order have different types. Therefore each non-empty queue contributes at most $1$ , and using three non-empty queues gives total score $3$ .

Case 4

One optimal final arrangement is A, BBBB, AA, B. The scores are $1$ , $4$ , $2$ , and $1$ , so the total score is $8$ .

Case 5

One optimal final arrangement is BB, AAA, BBAAB. The scores are $2$ , $3$ , and $2$ , so the total score is $7$ . A higher total cannot be achieved with only three queues.

Output

Case 1

Case 2

Case 3

Case 4

Case 5

There are $n$ people standing in $m$ queues. Each person has type A or type B.

The queues are numbered from $1$ to $m$ . In each queue, people have an order from the front to the back.

You may perform the following operations any number of times, in any order:

If $i > 1$ and queue $i$ is not empty, take the person at the front of queue $i$ and move them to the back of queue $i-1$ .
If $i < m$ and queue $i$ is not empty, take the person at the back of queue $i$ and move them to the front of queue $i+1$ .

The score of an empty queue is $0$ .

Your task is to maximize the sum of scores of all queues after performing any number of operations.

$1 \le t \le 10^4$
$1 \le m \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 10^5$
The sum of $m$ over all test cases is at most $2 \times 10^5$
Each initial queue is non-empty.
The total number of characters in the $m$ given strings of a test case is exactly $n$ .
Each string consists only of characters A and B.

t

\left. \begin{array}{l} n \quad m \\ s_1 \\ s_2 \\ \vdots \\ s_m \end{array} \right\} \times t

For each test case, $s_i$ describes the initial state of queue $i$ from front to back.

\left. \begin{array}{l} \mathrm{ans} \end{array} \right\} \times t

For each test case, output the maximum possible sum of scores of all queues.

Keeping the queues unchanged gives scores $2$ and $2$ , so the sum is $4$ . No arrangement with two queues can make the total score equal to $5$ .

All people have type A, so all $4$ people can be counted in the front blocks of the queues.

Every two adjacent people in the global order have different types. Therefore each non-empty queue contributes at most $1$ , and using three non-empty queues gives total score $3$ .

One optimal final arrangement is A, BBBB, AA, B. The scores are $1$ , $4$ , $2$ , and $1$ , so the total score is $8$ .

One optimal final arrangement is BB, AAA, BBAAB. The scores are $2$ , $3$ , and $2$ , so the total score is $7$ . A higher total cannot be achieved with only three queues.

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

14B. Queue Fronts

Constraints

Input

Output

Samples

14B. Queue Fronts

Constraints

Input

Output

Samples