32293번 - ABB to BA (Hard)

문제

이 문제는 "ABB to BA"의 어려운 버전입니다. 두 버전은 $t$와 $n$의 제한을 제외하고 동일합니다.

'A'와 'B'만으로 이루어진 문자열 $S$가 주어집니다. 여러분은 다음 동작을 더 이상 수행할 수 없을 때까지 반복해야 합니다.

• $S$에서 첫 번째로 부분 문자열 "ABB"가 등장한 위치를 $i$라고 할 때, 이 위치의 부분 문자열 "ABB"를 지우고 "BA"로 바꿉니다.
• 다시 말해, $S_iS_{i+1}S_{i+2}$가 "ABB"인 가장 작은 $i$를 찾아, $S_i$와 $S_{i+1}$을 각각 'B'와 'A'로 바꾸고 $S_{i+2}$를 $S$에서 지웁니다.
• $S$에 "ABB"가 부분 문자열로 등장하지 않는다면 동작을 수행할 수 없습니다.

반복이 끝난 후 $S$의 내용을 출력하는 프로그램을 작성해 주세요.

입력

각 입력은 여러 개의 테스트 케이스로 구성됩니다. 입력의 첫 번째 줄에 테스트 케이스의 개수 $t$가 주어집니다. (1ドル \le t \le 5 \cdot 10^4$)

이후 테스트 케이스의 정보가 주어지며, 각 테스트 케이스의 입력은 다음과 같이 두 줄로 구성됩니다.

• 첫 번째 줄에 $S$의 길이를 나타내는 정수 $n$이 주어집니다. (1ドル \le n \le 5\cdot 10^5$)
• 두 번째 줄에 길이 $n$의 문자열 $S$가 주어집니다. ($S_i$는 모두 'A' 또는 'B')

모든 테스트 케이스에 대한 $n$의 합이 5ドル\cdot 10^5$을 초과하지 않습니다.

출력

각 테스트 케이스에 대해 반복이 끝난 후 $S$의 내용을 한 줄에 출력합니다.

제한

힌트