{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThere are three types of \u003ci\u003e\u003cb\u003e“perfect bracket sequences”\u003c/b\u003e\u003c/i\u003e:\n\u003col\u003e\n\u003cli\u003e\u0027(\u0027 + perfect bracket sequence + \u0027)\u0027 \u003c/li\u003e\n\u003cli\u003e\u0027[\u0027 + perfect bracket sequence + \u0027]\u0027 \u003c/li\u003e\n\u003cli\u003ePerfect bracket sequence + Perfect bracket sequence.\u003c/li\u003e\n\u003c/ol\u003e\n\u003c/p\u003e\n\u003cp\u003eMohammed has been hired to delete “perfect bracket sequences” from a given string. \n\nThe company keeps track of how many perfect bracket sequences he deletes, and pays him according to the total amount of sequences he deletes from the string.\n\nHelp Mohammed by writing a program that automatically deletes the \u003cb\u003eMAXIMUM \u003c/b\u003eamount of perfect bracket sequences from a given string \u003ci\u003es\u003c/i\u003e.\n\u003c/p\u003e\n\n\n"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003efirst line contains an integer $$$t$$$ ($$$1 \\le t \\le 1000$$$)\u0026nbsp;— the number of test-cases.\u003c/p\u003e\n\u003cp\u003eThen T lines, each containing a non-empty string s consisting of the following characters: ‘(‘ , ‘)’ , ‘[‘ , and ‘]’ ..\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test-case, print the \u003cb\u003eMAXIMUM\u003c/b\u003e amount of perfect bracket sequences that Mohammed can delete.\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n()\n[]()\n([)]\n)]([\n)[(]\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n2\n2\n0\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first test case, you can erase ().\n\u003c/p\u003e\n\u003cp\u003eIn the second test case, you can remove the whole string since it consists of Perfect Bracket Sequence+Perfect Bracket Sequence, but since you want the maximum amount of deletions you can delete the [] first then delete the () afterward.\u003c/p\u003e\n\u003cp\u003eIn the third test case, you can erase the brackets on index 0 and 2 () and then the brackets on index 1 and 3 [] .\u003c/p\u003e\n"}}]}