Có một đường đi gồm \(n\) ô vuông liên tiếp nhau và được đánh số từ \(1\) đến \(n\). Mỗi ô vuông có thể hoặc là trống rỗng, hoặc có sừng nhọn hoặc có vàng.
Ở mỗi bước di chuyển, hoặc bạn có thể di chuyển 1 hoặc 2 ô dọc theo đường đi nhưng phải đảm bảo rằng, ô mà bạn muốn di chuyển tới không có sừng nhọn.
Nếu bạn di chuyển đến ô có vàng, thì hãy nhặt nó lên.
Nhiệm vụ của bạn là hãy nhặt càng nhiều vàng càng tốt và hãy in số lượng vàng lớn nhất đó ra màn hình. Biết rằng, ban đầu bạn ở ô số 1 - Là ô mặc định là trỗng rỗng.
Để hiểu hơn, bạn đi đến ví dụ sau:
Giả sử ta có xâu \(s\) có độ dài là \(10\) thể hiện bản đồ đường đi như sau: \(.@@*@.**@@\), trong đó:
++ Dấu "." : Thể hiện ô trống rỗng
++ Dấu "@" : Thể hiện ô có vàng
++ Dấu "*" : Thể hiện ô có sừng nhọn
(Bạn có thể xem hình minh hoạ bên dưới)
Và với cách di chuyển như trên, thì số vàng tối đa mà mình có thể thu được là 3.
Input
- Dòng đầu tiên chứa số nguyên dương \(t(1\le t\le 1000)\) - Thể hiện số testcase
- \(t\) block tiếp theo, mỗi block có dạng như sau:
++ Dòng đầu tiên chứa số nguyên dương \(n(1\le n\le 50)\) - Thể hiện độ dài của đường đi
++ Dòng thứ hai chứa xâu \(s\) gồm có \(n\) kí tự thể hiện bản đồ đường đi
Output
- Ứng với mỗi testcase, hãy in kết quả ra màn hình.
Example
Test 1
Input
2
10
.@@*@.**@@
3
.@.
Output
3
1
Bình luận