In the city where you live, Kickstartland, there is particularly long street with houses on it. This street has length , and the houses are evenly placed along it, that is, the st house is at position , the nd house is at position , and so on. The distance between any pair of houses and is , where denotes the absolute value of .
Some of these houses have trash bins in front of them. That means that the owners of such houses do not have to walk when they want to take their trash out. However, for the owners of houses that do not have trash bins in front of them, they have to walk towards some house that has a trash bin in front of it, either to the left or to the right of their own house.
To save time, every house owner always takes their trash out to the trash bin that is closest to their houses. If there are trash bins that are both the closest to a house, then the house owner can walk to any of them.
Given the number of houses , and the description of which of these houses have trash bins in front of them, find out what is the sum of the distances that each house owner has to walk to take their trashes out. You can assume that at least house has a trash bin in front of it.
输入格式
The st line of the input gives the number of test cases, . test cases follow. Each test case consists of lines.
The st line of each test case contains an integer , denoting the number of houses on the street.
The nd line of each test case contains a string of length , representing which houses have trash bins in front of them. If the -th character in string is equal to , then it means that the -th house has a trash bin in front of it. Otherwise, if it is equal to , then it means that the -th house does not have a trash bin in front of it.
输出格式
For each test case, output one line containing Case #: , where is the test case number (starting from ) and is the sum of the distances that each house owner has to walk to take their trashes out.
样例
样例输入 1
2
3
111
6
100100
样例输出 1
Case #1: 0
Case #2: 5
数据范围与提示
For the st test case, every house has a trash bin in front of it, and therefore none of the house owners will have to walk to take their trashes out.
For the nd test case, the st and the th house owners have trash bins in front of their houses, and therefore will not have to walk. The nd house owner will walk towards the st house, and the distance will be equal to . The rd, th, and th house owners will walk towards the th house, and the distances will be equal to , , and , respectively.
