提示: 欢迎访问OurACM平台。
Problem 1906 Special Sequence

Accept: 63    Submit: 162
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

There is a sequence that only consists of characters ‘/’ and ‘\’. You should calculate the number of down sequences and up sequences respectively in the given sequence.

A down sequence is defined as follows:

1. “\/” is a down sequence.

2. If S is a down sequence, then “\S/” is also a down sequence.

3. Any other sequences are not a down sequences.

Similarly, an up sequence is defined as follows:

1. “/\” is an up sequence.

2. If S is an up sequence, then “/S\” is also an up sequence.

3. Any other sequences are not an up sequences.

For example, sequences “/\”, “//\\” and “///\\\” are all up sequences, while “\/”, “/\\” and “/\/\” are not. Sequences “\/”, “\\//” and “\\\///” are all down sequences, while “/\”, “\//” and “\/\/” are not. There is only one down sequence in the sequence “\//\\”, that is “\/”. There are two up sequences in the sequence “\//\\”, they are “/\” and “//\\”.

Your task is to solve this problem.

Input

The first line of the input contains an integer T (T <= 10), indicating the number of cases. Each case begins with a line containing one integer n (1n100), the length of the sequence. The next line contains the sequence, consisting of characters ‘/’ and ‘\’.

Output

For each test case, print a line containing the test case number (beginning with 1) and two numbers separated by a space indicating the number of down sequences and up sequences respectively in the given sequence.

Sample Input

3 2 /\ 7 //\//\\ 15 ///\/\/\//\\///

Sample Output

Case 1: 0 1 Case 2: 1 3 Case 3: 5 5

Source

2010年全国大学生程序设计邀请赛(福州)热身赛

Submit  Back  Status  Discuss