Đặc vụ P là một đặc vụ bí mật làm việc cho tổ chức O.W.C.A. (Organization Without a Cool Acronym). Với bộ dạng là một con thú mỏ vịt bình thường, đặc vụ P luôn có hai danh tính mà làm cho kẻ thù của mình là Tiến sĩ Heinz Doofenshmirtz lúc nào cũng nhầm lẫn:

• ~\mathrm{\color{orange}{A}\ \color{darkcyan}{Platypus}}~ (?) – đây là danh tính thường ngày của đặc vụ P. Nếu như không cải trang thêm gì, Tiến sĩ Doofenshmirtz sẽ nghĩ đặc vụ P chỉ là một con thú mỏ vịt bình thường.

• ~\mathrm{\color{orange}{Perry}\ \color{brown}{the}\ \color{darkcyan}{Platypus}}~ (?!?) – đây là danh tính mà đặc vụ P sử dụng khi hành động. Tiến sĩ Doofenshmirtz luôn nhận ra ngay đây là đặc vụ P với danh tính này.

Mới đây đặc vụ P đã nhận được một thông điệp từ Tiến sĩ Doofenshmirtz. Thông điệp là một xâu kí tự ~s~ đã được mã hóa, chỉ bao gồm các kí tự a, p và t. Thoạt nhìn qua thì thông điệp có đề cập đến đặc vụ P. Nhưng do không phân biệt được 2 danh tính của đặc vụ, nên lúc thì Tiến sĩ sử dụng ~\mathtt{\color{orange}a\color{darkcyan}p}~, lúc thì dùng ~\mathtt{\color{orange}p\color{brown}t\color{darkcyan}p}~ trong thông điệp của mình.

Đặc vụ P cần nén thông điệp này để gửi về O.W.C.A. phân tích tiếp. Để làm điều này mà không làm mất đi ý nghĩa của thông điệp, đặc vụ P có thể sử dụng một trong hai thao tác sau (không hoặc nhiều lần):

• Chọn một xâu con~^*~ ~\mathtt{\color{orange}a\color{darkcyan}p}~ của ~s~ và thay nó bằng ~\mathtt{\color{orange}p\color{brown}t\color{darkcyan}p}~.

• Chọn một xâu con ~\mathtt{\color{orange}p\color{brown}t\color{darkcyan}p}~ của ~s~ và thay nó bằng ~\mathtt{\color{orange}a\color{darkcyan}p}~.

Cho thông điệp ~s~ của tiến sĩ Heinz Doofenshmirtz. Hãy giúp đặc vụ P tìm xem, nếu sử dụng hai thao tác trên, thì thông điệp được nén có độ dài nhỏ nhất có thể là bao nhiêu.

~^*~ Xâu ~t~ được gọi là xâu con của ~s~ nếu như ~t~ có thể được tạo thành bằng cách xóa đi (không hoặc nhiều) ký tự ở đầu ~s~, và xóa đi (không hoặc nhiều) ký tự ở cuối ~s~.

Input

Dòng đầu tiên gồm số nguyên ~t~ (~1 \le t \le 10\,000~) – số lượng testcase. Mô tả của mỗi testcase như sau.

Dòng đầu tiên và duy nhất của testcase chứa xâu ~s~ (~1 \le |s| \le 2 \cdot 10^5~, ~s_i \in \{ \mathtt{a}, \mathtt{p}, \mathtt{t} \}~) – thông điệp ban đầu của tiến sĩ Doofenshmirtz.

Đảm bảo rằng tổng ~|s|~ qua các testcase không quá ~2 \cdot 10^5~.

Output

Với mỗi testcase, in ra một số nguyên là độ dài nhỏ nhất của thông điệp đã nén, sử dụng hai thao tác mô tả trong đề bài.

Scoring

Tổng điểm cho bài này là ~1750~.

Sample Input 1

3
ptp
apapapap
aptapt

Sample Output 1

2
8
5

Notes

Trong testcase đầu tiên, thông điệp ~s = \mathtt{ptp}~. Đặc vụ P có thể biến cả thông điệp thành xâu ~s = \mathtt{ap}~, với độ dài xâu là ~2~.

Trong testcase thứ hai, thông điệp ~s = \mathtt{apapapap}~. Có thể chỉ ra rằng đây là thông điệp ngắn nhất có thể, nên đáp án cho testcase thứ hai này là ~8~.

Trong testcase thứ ba, thông điệp ~s = \mathtt{aptapt}~. Đặc vụ P có thể thực hiện nén thông điệp như sau:

• ~\mathtt{apt\color{orange}a\color{darkcyan}pt} \to \mathtt{apt\color{orange}p\color{brown}t\color{darkcyan}pt}~;

• ~\mathtt{a\color{orange}p\color{brown}t\color{darkcyan}ptpt} \to \mathtt{a\color{orange}a\color{darkcyan}ptpt}~;

• ~\mathtt{aa\color{orange}p\color{brown}t\color{darkcyan}pt} \to \mathtt{aa\color{orange}a\color{darkcyan}pt}~.