Perhaps some of you are familiar 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, cannon, situated next to the gutter, has some stock of colorful balloons, and occasionally throws them into the gutter. Abandoned balls embedded in a row. If after a shot in the trough formed by a continuous sequence of three or more balls of one color, which includes an abandoned ball, then they disappear, and the neighboring balls are moved, linking number (see fig. down). If, after the disappearance of the balls in place of the joint adjacent spheres form a continuous sequence of three or more balls of one color, they will also disappear, and so on. Purpose of the game - to destroy all the balls. \includegraphics{https://static.e-olymp.com/content/0c/0ca96b789bfa241720005a9a69a67b02e1d5d5c6.jpg} Number the balls from left to right, starting with the unit. Shot the ball in position \textbf{n} means that it appears to the right of the ball with the number \textbf{n} and will be in position \textbf{n }\textit{\textbf{+1.}} Non balls, located to the right of the ball had flown, increased by one. Landing the ball to the left of the entire series is denoted by the position number \textbf{0.} After the disappearance of some of the balls, balls in the gutter re-numbered from left to right, starting with the unit. Need to write a program that defines the optimal strategy of shooting. The optimal strategy is one in which the smallest number of rounds leads to the disappearance of all balls, and if some of these strategies, the chosen one in which the first shot is made as soon as possible to the left, and if more than one and such a comparison is on the second shot, etc. \InputFile The first line of input contains the number of tests. Each test consists of one line describing a number of balls, the color of each ball is described by the capital letter alphabet \textbf{(A} .. \textbf{Z).} Test number \textbf{1} and its solution is shown in the illustration. It is known that the length of a number of ≤ \textbf{14,} and for the destruction of a number of required ≤ \textbf{10} shots, if you follow the optimal strategy. \OutputFile For each test in the output file output line: first, the minimum number of shots, then through the gap, the number of pairs of letters: the color of the ball and the position of the shot. Shots in the response should be listed in the order they appear in the game.