You have recently started to study how to paint, and in one of the first classes you learned about the three primary colors: Red, Yellow, and Blue. If you combine these colors, you can produce many more colors. For now, the combinations that you have studied are the following:
You still do not understand shades of colors, therefore the proportion and order of each color in the combination does not matter. For example, combining Red and Yellow produces the same result as combining Yellow and Red, as well as the same result as combining Red, Yellow, and Red again.
To practice your skills, you want to paint a -dimensional painting of length . Your painting consists of squares. From left to right, represents the color of the -th square. Initially all squares are Uncolored, that is, for every .
In a single stroke, you can choose one of the three primary colors and apply it to a sequence of consecutive squares. In other words, you can choose a color and two integers and , such that , and apply color to all squares such that . If the square being painted is currently Uncolored, then its color will become . Otherwise, the color will be a combination of all the colors applied on this square so far and the new color , as described in the list above.
In order to save time, you want to use as few strokes as possible. Given the description of the painting that you want to paint, figure out what is the minimum number of strokes required to paint it.
输入格式
The first line of the input gives the number of test cases, . test cases follow.
Each test case starts with a line containing an integer , representing the length of the painting. Then on the next line, there will be a string of length , representing the painting. The -th character represents the color of square , according to the following list:
输出格式
For each test case, output one line containing Case #: , where is the test case number (starting from ) and is the minimum number of strokes required to paint the painting.
