타일 게임

각 타일에는 1 이상 100 이하의 숫자와 색 하나가 적혀 있다. 색은 빨간색, 노란색, 초록색, 파란색 중 하나이며, 타일 정보는 숫자 뒤에 색을 나타내는 소문자를 붙여 표현한다. 예를 들어 1r은 숫자 1이 적힌 빨간색 타일이고, 3y는 숫자 3이 적힌 노란색 타일이다. 색 문자는 r(빨간색), y(노란색), g(초록색), b(파란색)을 뜻한다.

이 타일들로 게임을 한다. 같은 색이면서 숫자가 연속된 타일을 3개 이상 골라 제거하면, 제거한 타일에 적힌 숫자의 합만큼 점수를 얻는다. 예를 들어 9r, 10r, 11r을 제거하면 30점을 얻고, 60g, 61g, 62g, 63g, 64g, 65g를 제거하면 375점을 얻는다.

또한 숫자가 같고 색이 모두 다른 타일을 3개 이상 골라 제거해도, 제거한 타일에 적힌 숫자의 합만큼 점수를 얻는다. 예를 들어 1r, 1g, 1b를 제거하면 3점을 얻고, 17r, 17g, 17b, 17y를 제거하면 68점을 얻는다.

선택한 타일은 반드시 제거되며, 제거된 타일은 다시 사용할 수 없다. 주어진 타일들을 규칙에 맞게 제거해서 얻을 수 있는 최대 점수를 구하라.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

• 첫째 줄에 타일의 개수 N이 주어진다. (1 <= N <= 400)
• 둘째 줄에 공백으로 구분된 N개의 타일 정보가 주어진다. 각 타일의 숫자는 1 이상 100 이하이며, 같은 타일은 두 번 주어지지 않는다.

각 테스트 케이스마다 얻을 수 있는 최대 점수를 한 줄에 하나씩 출력한다.