Phân hoạch một xâu là cách chia xâu thành một hoặc nhiều xâu con liên tiếp, không rỗng và đôi một không giao nhau, sao cho ghép chúng theo thứ tự ban đầu sẽ thu lại xâu gốc. Gọi mỗi xâu con là một khối; độ dài của phân hoạch là số khối.

Một phân hoạch được gọi là đối xứng nếu dãy các khối tạo thành một palindrome khi xem mỗi khối như một phần tử không thể chia nhỏ. Ví dụ, xâu decode có các phân hoạch đối xứng (de)(co)(de) và (decode). Mọi xâu đều có phân hoạch đối xứng tầm thường chỉ gồm một khối.

Với mỗi xâu được cho, hãy tìm số khối lớn nhất có thể trong một phân hoạch đối xứng.

Dữ liệu vào

Dòng đầu chứa số nguyên \(t\) (\(1\le t\le10\)), là số bộ kiểm thử.

Mỗi dòng trong \(t\) dòng tiếp theo chứa một xâu \(s\) chỉ gồm các chữ cái tiếng Anh viết thường. Gọi \(n\) là độ dài của xâu \(s\); ta có \(1\le n\le10^6\).

Dữ liệu ra

Với mỗi bộ kiểm thử, in một dòng chứa số khối lớn nhất của một phân hoạch đối xứng.

Ví dụ

4
bonobo
deleted
racecar
racecars

3
5
7
1

Phân nhóm

1. \(15\) điểm: \(n\le30\).
2. \(20\) điểm: \(n\le300\).
3. \(25\) điểm: \(n\le10000\).
4. \(40\) điểm: Không có ràng buộc bổ sung.