{"code":"palpartition","name":"Phân tích đối xứng","description":"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 đó.\r\n\r\nChú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)`.\r\n\r\nMộ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$.\r\n\r\nVớ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é!\r\n\r\n####Input\r\n\r\n- Dòng đầu tiên chứa số nguyên dương $t$ thể hiện số câu hỏi.\r\n\r\n- $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.\r\n####Output\r\n\r\n- 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.\r\n\r\n####Scoring\r\n\r\nGọi $n$ là độ dài của xâu $s$.\r\n\r\n- $1\\leq t\\leq 10$.\r\n- $1\\leq n\\leq 10^6$.\r\n- Sutask $1$ ($15\\%$ số điểm): $n\\leq 30$.\r\n- Sutask $2$ ($20\\%$ số điểm): $n\\leq 300$.\r\n- Sutask $3$ ($25\\%$ số điểm): $n\\leq 10,000$.\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n\r\n        ```sample\r\n        4\r\n        bonobo\r\n        deleted\r\n        racecar\r\n        racecars\r\n        ```\r\n\r\n    ???+ success \"Output\"\r\n\r\n        ```sample\r\n        3\r\n        5\r\n        7\r\n        1\r\n        ```","points":300.0,"partial":true,"time_limit":2.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}