I have a friend named Dian. She is expert in giving miscall. When she starts giving miscall to any of her friends she doesn’t stop before 10 to 20 (sometimes more). We guess she has software for giving miscall. Otherwise how it is possible to give continuously as many miscall for a human being!

One day I decided to count how many miscall she can give at a time. But it’s really tough. Because sometimes I may have another phone call at the time of counting or I may receive her miscall thinking other’s call. After receiving any of her miscall I should start counting again since I want to count her maximum number of continuous miscall. But I shouldn’t do this after receiving other’s call or miscall. Could you help me in this job?

Input

First line of input contains the number of cases T (0 < T ≤ 100).

Each case contains a line consisting of four special character ‘.’, ‘*’, ‘#’ and ‘^’. Where ‘.’ denotes Dian’s miscall, ‘*’ denotes other’s miscall, ‘#’ denotes the received call of Dian and ‘^’ denotes the other’s receive call. Each line may contain at most 100000 characters.

Output

For each set of input, output a line containing case number followed by n where n is the maximum number of continuous miscall.

Sample

Input:
2
#...*...
...#...*...

Output:
Case 1: 6
Case 2: 6