An và Bảo cực kì yêu thích một chuỗi kí tự s chỉ chứa các kí tự in thường trong bảng chữ cái Latin. Hai bạn muốn sử dụng ba cây bút màu đen, đỏ, và xanh dương để viết chuỗi này lên bảng trắng. An và Bảo cảm thấy chuỗi kí tự này sẽ trở nên vô cùng kì diệu nếu tất cả các điều kiện sau đây được thỏa mãn:

1.      Mỗi kí tự trong chuỗi viết bằng đúng một màu (đen, đỏ, và xanh);

2.      Hai kí tự có cùng màu đỏ hoặc xanh thì phải khác nhau;

3.      Số lượng kí tự có màu xanh phải bằng số lượng kí tự có màu đỏ;

4.      Số lượng kí tự có màu xanh hoặc đỏ là nhiều nhất nhưng vẫn phải đáp ứng 3 điều kiện trên.

Ví dụ: Xem xét chuỗi “chuoikitukidieu”. Một trong những cách để chuỗi này sẽ trở nên kì diệu là viết như sau “chuoikitukidieu”.

An và Bảo muốn tự mình tìm ra cách để viết chuỗi kí tự yêu thích của mình một cách thật kì diệu. Tuy nhiên, hai bạn còn quá nhỏ nên cần một tí gợi ý. Bạn hãy giúp hai bạn nhỏ này bằng cách cho hai bạn ấy biết số k – số lượng kí tự được viết bằng màu đỏ (hoặc xanh, số lượng kí tự được viết bằng hai màu này bằng nhau) để chuỗi yêu thích trở nên kì diệu.

Đầu vào

Dòng đầu tiên cho một số nguyên t (1 ≤ t ≤ 1000) – số lượng trường hợp. Sau đó sẽ có t dòng tương ứng với t trường hợp.

Mỗi trường hợp là một chuỗi kí tự s không rỗng chỉ chứa các kí tự in thường trong bảng chữ cái Latin. Một xâu sẽ không dài quá 50 kí tự.

Đầu ra