题目背景

有些人在发电厂里发电，发出只包含“啊吧啊吧”的怪叫。

你想要知道他的发电水平，于是你想要知道他说了几次“啊吧啊吧”。

由于声音过于嘈杂，你听到的声音变得支离破碎，于是，你退而求其次，你想要知道他的怪叫中最多有几个不相交的子序列是“啊吧啊吧”。

题目描述

给你一个只包含字符 a 和 b 的字符串，你需要求出最多有多少不相交的子序列 abab。不相交的定义为，对于 $s$ 中的每个字符，其最多处于一个子序列中。

输入格式

共 $T$ 组数据。

第一行一个正整数 $T$，表示数据组数。

接下来 $T$ 行，每行一个字符串 $s$，表示你需要求的答案的字符串。

输出格式

共 $T$ 行，每行一个非负整数，表示最多能取出多少个不相交的子序列。

样例一

input

5
abababab
aabbaabb
abbbabbb
aaabaaab
abbababbbabbaaababbabbaabababbab

output

2
2
1
1
7

数据范围

令 $n$ 为输入的字符串长度的最大值。

对于 $10\%$ 的数据，$n\leq10$。

对于 $30\%$ 的数据，$n\leq100$。

对于 $50\%$ 的数据，$n\leq10^3$。

对于 $70\%$ 的数据，$n\leq10^5$。

对于 $100\%$ 的数据，$n\leq10^7,1\leq T\leq5$。