Agent P is a secret agent working for the O.W.C.A. (Organization Without a Cool Acronym). Disguised as an ordinary platypus, Agent P has two identities that constantly confuse his enemy, Dr. Heinz Doofenshmirtz:

• ~\mathrm{\color{orange}{A}\ \color{darkcyan}{Platypus}}~ (?) – this is Agent P's everyday identity. Without any additional disguise, Dr. Doofenshmirtz would think Agent P is just a regular platypus.

• ~\mathrm{\color{orange}{Perry}\ \color{brown}{the}\ \color{darkcyan}{Platypus}}~ (?!?) – this is the identity Agent P uses when he is on a mission. Dr. Doofenshmirtz always recognizes Agent P immediately with this identity.

Recently, Agent P received a message from Dr. Doofenshmirtz. The message is an encoded string ~s~ consisting only of the characters a, p, and t. At first glance, the message seems to refer to Agent P. However, due to the inability to distinguish between the two identities of the agent, sometimes Dr. Doofenshmirtz uses ~\mathtt{\color{orange}a\color{darkcyan}p}~, and other times he uses ~\mathtt{\color{orange}p\color{brown}t\color{darkcyan}p}~ in his message.

Agent P needs to compress this message to send back to O.W.C.A. for further analysis. To do this without losing the meaning of the message, Agent P can use one of the following operations (zero or multiple times):

• Choose a substring~^*~ ~\mathtt{\color{orange}a\color{darkcyan}p}~ from ~s~ and replace it with ~\mathtt{\color{orange}p\color{brown}t\color{darkcyan}p}~.

• Choose a substring ~\mathtt{\color{orange}p\color{brown}t\color{darkcyan}p}~ from ~s~ and replace it with ~\mathtt{\color{orange}a\color{darkcyan}p}~.

Given the message ~s~ from Dr. Heinz Doofenshmirtz, help Agent P find out what the minimum possible length of the compressed message can be after using the two operations described in the problem.

~^*~ A string ~t~ is called a substring of ~s~ if ~t~ can be formed by deleting (zero or more) characters from the beginning of ~s~, and deleting (zero or more) characters from the end of ~s~.

Input

The first line contains an integer ~t~ (~1 \le t \le 10\,000~) – the number of test cases. Each test case is described as follows.

The first and only line of the test case contains the string ~s~ (~1 \le |s| \le 2 \cdot 10^5~, ~s_i \in \{ \mathtt{a}, \mathtt{p}, \mathtt{t} \}~) – the original message from Dr. Doofenshmirtz.

It is guaranteed that the total ~|s|~ across all test cases does not exceed ~2 \cdot 10^5~.

Output

For each test case, output an integer representing the minimum length of the compressed message, using the two operations described in the problem.

Scoring

The total score for this problem is ~1750~.

Sample Input 1

3
ptp
apapapap
aptapt

Sample Output 1

2
8
5

Notes

In the first test case, the message ~s = \mathtt{ptp}~. Agent P can transform the entire message into the string ~s = \mathtt{ap}~, with a length of ~2~.

In the second test case, the message ~s = \mathtt{apapapap}~. It can be shown that this is the shortest possible message, so the answer for this second test case is ~8~.

In the third test case, the message ~s = \mathtt{aptapt}~. Agent P can perform the message compression as follows:

• ~\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}~.