JNzH 十分讨厌一段字符串 A2345，尤其是 A 和 5 这两个字符。

给定 T 段只由 A 和 5 这两个字符组成的字符串，规定一段由 A 和 5 组成的字符串是恶心的当且仅当删去若干个字符后（也可以 0 个），剩下的字符串变成 AAA55。举例来说，AAA55, AA5A55, A5A5A55 就是恶心的，而 555AAA, A5A55A5AA 就不是恶心的。

现可以修改字符串里面的每个字符，A 可以修改成 5，而 5 又可以修改成 A ，问最少的修改次数使得这个字符串不会让 JNzH 感到恶心。

第一行输入一个整数 T \ (1 ≤ T≤ 1000) ，表示 T 组数据。

对于每组数据，输入包含一行只包含字符 A 和 5 的字符串 s \ (1≤|s|≤100)。

对于每组数据，输出一行一个整数表示最少的修改次数。

这里分别给出一种让修改次数最小的方案：

• AA555，修改了第 3 个字。
• AA555555A5，修改了第 4 个字。
• AA55555555，修改了第 3,4,5 个字。