Xét các cách chia một xâu ký tự \(s\) thành một hoặc nhiều xâu con liên tiếp và không giao nhau, ta gọi mỗi xâu con này là một mảnh. Độ dài của cách phân tích sẽ bằng số lượng mảnh trong cách phân tích đó.

Chúng ta có thể biểu diễn một cách phân tích bằng cách viết ra mỗi mảnh của nó trong một cặp ngoặc đơn. Ví dụ, xâu decode có thể được phân tích thành (d)(ec)(ode) hoặc (d)(e)(c)(od)(e).

Một cách phân tích gọi là đối xứng nếu các mảnh của nó tuần tự hợp thành một dãy đối xứng. Ví dụ, hai cách phân tích đối xứng duy nhất cho xâu decode là (de)(co)(de) và (decode). Hiển nhiên mỗi từ bất kỳ đều có thể được phân tích đối xứng thành một dãy có độ dài bằng \(1\).

Với một xâu \(s\) cho trước, bạn hãy xác định cách phân tích đối xứng có độ dài lớn nhất của nó nhé!

Input

• Dòng đầu tiên chứa số nguyên dương \(t\) thể hiện số câu hỏi.

• \(t\) dòng tiếp theo, mỗi dòng chứa duy nhất một xâu \(s\) chỉ gồm các ký tự latin in thường và không có dấu cách nào, thể hiện một câu hỏi.

Output

• Gồm \(t\) dòng, mỗi dòng in ra một số nguyên là độ dài lớn nhất của một cách phân tích đối xứng cho xâu ký tự tương ứng.

Scoring

Gọi \(n\) là độ dài của xâu \(s\).

• \(1\leq t\leq 10\).
• \(1\leq n\leq 10^6\).
• Sutask \(1\) (\(15\%\) số điểm): \(n\leq 30\).
• Sutask \(2\) (\(20\%\) số điểm): \(n\leq 300\).
• Sutask \(3\) (\(25\%\) số điểm): \(n\leq 10,000\).

Example

4
bonobo
deleted
racecar
racecars

3
5
7
1