Sherlock học rất nhanh và bắt đầu khoe khoang rằng anh ấy giỏi thế nào, vì vậy Waston đã đưa ra một bài toán để kiểm tra kiến thức của anh ta. Anh ấy yêu cầu Sherlock tạo ra một xâu ~S~ gồm ~L + R~ kí tự, trong đó có ~L~ dấu '~(~' và ~R~ dấu '~)~'. Hơn nữa, xâu tạo ra phải là xâu có nhiều xâu con là dãy ngoặc đúng nhất. (Hai xâu con được xem là khác nhau nếu chúng bắt đầu và kết thúc ở các vị trí khác nhau, cho dù hai xâu ấy bằng nhau). Lưu ý rằng ~S~ có thể không phải là một dãy ngoặc đúng.

Sherlock chắc chắn rằng một khi anh ấy đã biết số xâu con không rỗng tối đa là dãy ngoặc đúng thì anh ấy sẽ giải được bài toán. Bạn hãy giúp anh ấy tìm ra con số tối đa ấy nhé!

Input

Output

Sample Input

3
1 0
1 1
3 2

Sample Output

Case #1: 0
Case #2: 1
Case #3: 3

Scoring