Game Zuma#429
Perhaps some of you are familiar with the game Zuma, about the adventures of a frog. In this problem, the rules are similar and quite simple: in a stone trough is a series of colorful balls; a cannon, situated next to the trough, has a stock of colorful balls and occasionally throws them into the trough. Thrown balls are embedded in the row. If, after a shot, a continuous sequence of three or more balls of the same color forms in the trough, and this sequence includes the thrown ball, then these balls disappear, and the neighboring balls move together, closing the row (see the figure below). If, after the disappearance of balls, a new continuous sequence of three or more balls of the same color is formed at the place of the joint, those balls also disappear, and so on. The objective of the game is to destroy all the balls.
Number the balls from left to right, starting with . Shooting a ball into position means it will appear to the right of the ball with number and will be at position n + 1. The numbers of balls located to the right of the thrown ball increase by one. Placing the ball to the very left of the row corresponds to position number . After some balls disappear, the remaining balls in the trough are re-numbered from left to right, starting from .
You need to write a program that determines the optimal shooting strategy. The optimal strategy is one in which the smallest number of shots leads to the disappearance of all balls. If there are several such strategies, choose the one in which the first shot is as far to the left as possible, then (if still tied) compare by the second shot, and so on.
The first line contains the number of tests. Each test consists of a single line describing a sequence of balls; the color of each ball is represented by a capital Latin letter (). Test number and its solution is shown in the illustration. It is known that the length of the sequence is , and no more than shots are required to destroy the sequence using the optimal strategy.
For each test, output a single line: first, the minimum number of shots, then for each shot, a pair of letter and position separated by a space: the color of the ball and the position of the shot. The shots must be listed in the order they are made during the game.
Example 1