Your friend John just came back from vacation, and he would like to share with you a new property that he learned about strings.
John learned that a string of length consisting of uppercase English characters is strictly increasing if, for every pair of indices and such that (-based), the character at position is smaller than the character at position .
For example, the strings ABC and ADF are strictly increasing, however the strings ACC and FDA are not.
Now that he taught you this new exciting property, John decided to challenge you: given a string of length , you have to find out, for every position , what is the length of the longest strictly increasing substring that ends at position .
输入格式
The first line of the input gives the number of test cases, . test cases follow.
Each test case consists of two lines.
The first line contains an integer , representing the length of the string.
The second line contains a string of length , consisting of uppercase English characters.
输出格式
For each test case, output one line containing Case #x: followed by , where is the test case number (starting from ) and is the length of the longest strictly increasing substring that ends at position .
样例
样例输入 1
2
4
ABBC
6
ABACDA
样例输出 1
Case #1: 1 2 1 2
Case #2: 1 2 1 2 3 1
数据范围与提示
In Sample Case , the longest strictly increasing substring ending at position is A. The longest strictly increasing substrings ending at positions , , and are AB, B, and BC, respectively.
In Sample Case , the longest strictly increasing substrings for each position are A, AB, A, AC, ACD, and A.
