ABB to BA (어려운 버전)

이 문제는 "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$의 내용을 한 줄에 출력합니다.