[중등부] 2023 KOI 대비 모의고사 (4월 1주차)

소문자 알파벳으로만 구성된 문자열이 주어지면 해당 문자열에서 두 개의 연속된 문자를 제거한다.

이러한 작업 후에 나올 수 있는 다른 문자열의 종류가 몇 가지인지 출력하는 프로그램을 작성하시오.

예를 들어 "aaabcc"라는 문자열에서는 아래와 같이 네 가지 경우의 수가 나온다.

"abcc"(처음 두 개 또는 두 번째부터 문자 두 개 삭제), " aacc "(세 번째부터 문자 두 개 삭제)," aaac "(네 번째부터 문자 두 개 삭제) 및 " aaab "(마지막 두 개 삭제)

또한 "ab"라는 문자열이 주어진 경우 연속한 두 문자를 제거하면 "" 라는 빈 문자열이 된다.

이 경우 하나의 경우가 있는 것으로 간주한다.

입력

첫 번째 줄에는 테스트 케이스의 수 T가 입력된다. (1 ≤ T ≤ 10^4)

각 테스트 케이스의 첫 번째 줄에는 문자열의 길이 N이 입력된다. (3 ≤ N ≤ 10^5)

각 테스트 케이스의 두 번째 줄에는 문자열 S가 입력된다.

모든 테스트 케이스에 대해 길이의 총 합이 2*10^5을 넘지 않는다.

출력

두 개의 연속된 문자를 제거하여 나올 수 있는 문자열의 종류가 몇 가지인지 출력하시오.

두 문자 제거 (delete two characters)
서브태스크

2초 256MB