Cách làm tối ưu là thực hiện thao tác ~\texttt{ap} \to \texttt{ptp}~ theo thứ tự từ phải qua trái. Sau đó thực hiện thao tác ~\texttt{ptp} \to \texttt{ap}~ theo thứ tự từ trái sang phải.

Dưới đây là một số quan sát để nhận thấy tại sao cách làm trên đúng. Phần chứng minh xin nhường lại cho độc giả:

• Tổng số kí tự a và t trong cả xâu là hằng số.
• Có thể nhận thấy lúc nào cũng có thể biến đổi ~\texttt{ap} \to \texttt{ptp}~. Ta lúc nào cũng có thể biến đổi ~\texttt{ptp}~ này ngược lại về ~\texttt{ap}~ do nhóm 3 kí tự này không thể bị thay đổi tiếp bởi thao tác ~\texttt{ap} \to \texttt{ptp}~~\texttt{ap} \to \texttt{ptp}~ khác.
• Khi thực hiện ~\texttt{ap} \to \texttt{ptp}~ từ trái qua, ta có thể biến đổi nhóm kí tự ptaaaa...aaap thành ptptptpt...ptp. Khi áp dụng ~\texttt{ptp} \to \texttt{ap}~ theo thứ tự từ trái sang phải, ta có thể khử kí tự t đầu tiên, biến nó thành aaaaaaa...aaap. Chỉ có nhóm kí tự loại này bị thay đổi như vậy, đó cách làm sẽ cho ra xâu kí tự nhỏ nhất.

use std::io::*;

// Note:
// - This function consume s
// - The returned value is **reversed**.
fn do_replace(mut s: Vec<u8>, from: &[u8], to: &[u8]) -> Vec<u8> {
    let mut t = vec![];
    while s.len() > 0 {
        if s.ends_with(from) {
            s.truncate(s.len() - from.len());
            s.extend_from_slice(&to);
        } else {
            t.push(s.pop().unwrap());
        }
    }
    t
}

fn main() {
    let mut writer = std::io::BufWriter::new(stdout().lock());
    let stdin = stdin();
    let read_line = || {
        let mut input = String::new();
        stdin.read_line(&mut input).unwrap();
        input.trim().to_string()
    };

    let t = read_line().parse::<usize>().unwrap();

    for _ in 0..t {
        let s = read_line();
        let s = s.trim().as_bytes().to_vec();
        let s = do_replace(s, b"ap", b"ptp");
        let s = do_replace(s, b"ptp", b"pa"); // because we reversed the string
        writeln!(writer, "{}", s.len()).unwrap();
    }
}