Cho dãy các phép tính số học chỉ gồm các phép cộng trừ các số nguyên không âm. Ví dụ :
- ~1 - 2 + 3 - 4 - 5~
Bạn được phép đặt các dấu ngoặc '(', ')' vào dãy phép tính mà ko được thay đổi các dấu cộng trừ. Với các cách đặt khác nhau bạn có thể sẽ được các kết quả khác nhau. Ví dụ :
- ~1 - 2 + 3 - 4 - 5 = -7~
- ~1 - (2 + 3 - 4 - 5) = 5~
- ~1 - (2 + 3) - 4 - 5 = -13~
- ~1 - 2 + 3 - (4 - 5) = 3~
- ~1 - (2 + 3 - 4) - 5 = -5~
- ~1 - (2 + 3) - (4 - 5) = -3~
Câu hỏi đặt ra cho bạn là có bao nhiêu giá trị khác nhau có thể nhận được bằng cách đặt các dấu ngoặc vào dãy phép tính như trên?
Input
Mỗi test gồm ~5~ test nhỏ, mỗi test nhỏ là ~1~ dãy phép tính gồm ~N~ số nguyên ko âm ~(N \le 30)~ được ghi trên ~1~ dòng, các số được nối bởi dấu cộng hoặc trừ. Không có dấu trừ ở đầu dãy và không có dấu cách. Các số trong test ~\le 100~.
Output
Với mỗi bộ test ghi ra số lượng giá trị khác nhau nhận được bằng cách thêm dấu ngoặc vào dãy phép tính. Kết quả mỗi bộ test in trên 1 dòng.
Giới hạn
Có ~50\%~ số test ~N \le 10~
Sample Input
1-2+3-4-5
38+29-91
54-18+22+74
Sample Output
6
1
3
Bình luận