Nhà Bánh Kẹp Vô Hạn vừa giới thiệu một loại bánh mới! Một mặt bánh có khuôn mặt vui vẻ bằng vụn sô-cô-la (“mặt vui”), mặt kia không có gì (“mặt trống”).

Bạn là trưởng phục vụ đang trực và nhà bếp vừa đưa một chồng bánh để phục vụ khách. Như mọi người phục vụ bánh giỏi, bạn có thị lực tia X và biết mỗi chiếc đang ngửa mặt vui hay mặt trống. Bạn nghĩ khách sẽ vui nhất nếu khi phục vụ, mọi chiếc bánh đều ngửa mặt vui.

Bạn biết thao tác sau: cẩn thận nhấc một số chiếc ở đỉnh chồng (có thể là toàn bộ), lật cả nhóm, rồi đặt lại lên những chiếc không nhấc. Cả nhóm được lật trong một chuyển động, không lật riêng từng chiếc. Chính xác hơn, đánh số bánh \(1,2,\ldots,N\) từ trên xuống dưới và chọn \(i\) chiếc đầu. Sau khi lật, thứ tự là \(i,i-1,\ldots,2,1,i+1,\ldots,N\). Các bánh \(1\) đến \(i\) đổi mặt đang ngửa; các bánh \(i+1\) đến \(N\) giữ nguyên mặt.

Ký hiệu mặt vui là +, mặt trống là -. Với chồng --+- từ trên xuống, có thể nhấc ba chiếc đầu, lật cả nhóm rồi đặt lên chiếc thứ tư không đổi, thu được -++-. Những thao tác hợp lệ khác là lật một, hai hoặc cả bốn chiếc đầu. Không được lật hai chiếc ở giữa hay riêng chiếc cuối vì chỉ được lấy một đoạn bắt đầu từ đỉnh.

Bạn sẽ không phục vụ cho đến khi mọi bánh đều ngửa mặt vui, nhưng không muốn bánh nguội. Nếu luôn lựa chọn tối ưu, cần ít nhất bao nhiêu thao tác?

Dữ liệu vào

Dòng đầu chứa \(T\). Mỗi bộ test gồm một chuỗi \(S\); mỗi ký tự là + (ban đầu ngửa mặt vui) hoặc - (ban đầu ngửa mặt trống). Đọc từ trái sang phải tương ứng với chồng bánh từ trên xuống dưới.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó \(x\) bắt đầu từ 1 và \(y\) là số thao tác nhỏ nhất để mọi bánh ngửa mặt vui.

Ràng buộc

• \(1\le T\le100\).
• Mọi ký tự của \(S\) là + hoặc -.

Phân nhóm

• Test Set 1 (Visible): \(1\le |S|\le10\).
• Test Set 2 (Hidden): \(1\le |S|\le100\).

Đ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ụ

5
-
-+
+-
+++
--+-

Case #1: 1
Case #2: 1
Case #3: 2
Case #4: 0
Case #5: 3

Nguồn

Google Code Jam 2016, Vòng loại, bài Revenge of the Pancakes.

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