Hôm qua là ngày chủ nhật, nên Ghnav đã thức xuyên đêm chơi trò chơi điện tử FO4. Do đó, hôm nay lên lớp cậu đã ngủ gật và bị đuổi ra ngoài cửa lớp. May thay, lớp bên cạnh cũng có Tèo vì nói chuyện nên cũng bị đuổi ra. Cả 2 liền quyết định nghĩ ra trò chơi gì đó để tiêu khiển. Vì cả 2 đều mang kẹo oishi 3 vị bạc hà, ổi, vải nên họ đã nghĩ ra trò chơi như sau: Xếp ngẫu nhiên các viên kẹo, tạo thành 1 dãy gồm ~N~ viên. Sau đó lấy 2 vị trí bất kì có 2 viên kẹo vị khác nhau và thay thế nó bằng viên kẹo vị còn lại. Ví dụ 2 viên kẹo vị ổi và bạc hà cạnh nhau thì sẽ thay thế bằng 1 viên kẹo vị vải.

Trong lúc đó, thầy Phund đi qua và quyết định đố cả 2 rằng bằng thao tác trên, hãy rút gọn dãy kẹo thành dãy có độ dài ngắn nhất có thể.

Yêu cầu: Tìm độ dài ngắn nhất của dãy kẹo sau khi thực hiện các thao tác rút gọn.

Input

• Dòng đầu tiên gồm số nguyên ~T~ là số bộ test (~1 \le T \le 100~);
• Mỗi bộ test, gồm 1 xâu kí tự biểu diễn dãy kẹo (có độ dài ~\le 100~), với 3 loại kí tự latin thường như sau:
  • Kí tự ‘a’ là vị bạc hà;
  • Kí tự ‘b’ là vị ổi;
  • Kí tự ‘c’ là vị vải.

Output

• Với mỗi test, in trên mỗi dòng là độ dài ngắn nhất của chuỗi rút gọn.

Sample Input 1

3
cab
bcab
ccccc

Sample Output 1

2
1
5