Tile Game

Each tile has a number from 1 to 100 and one color. The color is one of red, yellow, green, and blue. A tile is written as its number followed by a lowercase color letter. Thus, 1r is a red tile numbered 1, and 3y is a yellow tile numbered 3. The letters mean r for red, y for yellow, g for green, and b for blue.

You play a game with these tiles. If you remove at least three tiles that have the same color and consecutive numbers, you gain points equal to the sum of the numbers on those tiles. Removing 9r, 10r, and 11r gives 30 points, and removing 60g, 61g, 62g, 63g, 64g, and 65g gives 375 points.

You may also remove at least three tiles that have the same number and all have different colors. This also gives points equal to the sum of the numbers on those tiles. Removing 1r, 1g, and 1b gives 3 points, and removing 17r, 17g, 17b, and 17y gives 68 points.

A selected tile must be removed, and a removed tile cannot be used again. Find the maximum score obtainable by removing tiles according to the rules.

The first line contains the number of test cases T. Each test case is given as follows.

• The first line contains the number of tiles N. (1 <= N <= 400)
• The second line contains N tile descriptions separated by spaces. Each tile number is between 1 and 100 inclusive, and no identical tile appears more than once.

For each test case, print one line containing the maximum score that can be obtained.