Bạn đang ở trong một kho chứa rất lớn, gồm \(2^{40}\) vị trí lưu trữ xếp thành một vòng tròn.

Một chiếc xe tải có cần cẩu di chuyển dọc theo vòng tròn, lấy lên hoặc đặt xuống các thùng hàng theo một chương trình. Xe có nguồn thùng hàng không giới hạn, nên lúc nào cũng có thể đặt thêm thùng xuống.

Chương trình là một dãy các lệnh:

• b: lùi một vị trí;
• f: tiến một vị trí;
• u: lấy lên một thùng tại vị trí hiện tại;
• d: đặt xuống một thùng tại vị trí hiện tại;
• (: không làm gì;
• ): nếu vị trí hiện tại có nhiều hơn một thùng, quay lại dấu ( khớp gần nhất trong dãy lệnh và tiếp tục chương trình từ đó. Lệnh này không di chuyển xe.

Các lệnh ( và ) luôn đi thành cặp: một ( sẽ có một ) khớp với nó ở phía sau. Chương trình có nhiều nhất hai cặp như vậy; nếu có hai cặp thì chúng không lồng nhau. Vì thế chương trình thuộc đúng một trong các dạng: không có ngoặc; có một cặp; hoặc có một cặp hoàn chỉnh rồi sau đó là một cặp hoàn chỉnh khác. Các test mẫu có ví dụ cho cả ba trường hợp.

Trước khi xe bắt đầu chạy chương trình, mỗi vị trí có đúng một thùng.

Một cách bí ẩn, nếu xe lấy thùng cuối cùng khỏi một vị trí, một xe khác lập tức tới và đặt xuống 256 thùng! Tương tự, nếu xe đặt một thùng khiến vị trí đó có 257 thùng, một xe khác lập tức đi qua và lấy 256 thùng, để lại một thùng. Vì vậy, mỗi vị trí luôn có từ 1 đến 256 thùng.

Hỏi xe thực hiện tổng cộng bao nhiêu lần di chuyển tiến hoặc lùi trước khi đi tới cuối chương trình?

Dữ liệu vào

Dòng đầu là \(T\); mỗi trong \(T\) dòng sau là chương trình dài tối đa 2000.

Dữ liệu ra

In Case #X: Y, với \(Y\) là số lần xe di chuyển.

Ràng buộc

• \(1\le T\le20\), độ dài 1..2000.

Phân nhóm

• Nhỏ: tối đa một cặp ngoặc.
• Lớn: tối đa hai cặp ngoặc.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
ufffdddbbbdd
dddd(fdbu)fff
dddd(fdddddbu)f(fdddddbu)
bf

Case #1: 6
Case #2: 11
Case #3: 49
Case #4: 2

Nguồn

Google Code Jam 2015, Chung kết thế giới, bài Crane Truck.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.