{"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":"前几天富哥和尹帝抛下队友王公子,选择和卓哥一起去打maimai,悲伤的王公子决定一个人在602做题,可他太生气了没办法静下心来做题(平常都是富哥做字符串),你能帮他解决下面这个问题吗?\u003cbr\u003e\n给你一个长度为n的括号序列s,其中n是偶数(能被2整除)字符串s由n/2的开括号\u0027(\u0027和n/2的闭括号\u0027)\u0027组成。你每次可以选择其中一个括号将其移动到字符串的开头或结尾,你的任务是从s中找到获得正则括号序列所需的最小移动次数,可以证明在给定的约束条件下,这个答案总是存在的。\n\u003cbr\u003e\n回想一下正则括号序列是什么:\u003cbr\u003e\n“()”是正则括号序列;\u003cbr\u003e\n如果s为正则括号序列,则“(”+ s +“)”为正则括号序列;\u003cbr\u003e\n如果s和t是正则括号序列,那么s + t就是正则括号序列。\u003cbr\u003e\n例如,“()()”、“(())()”,“(())”和“()”是正则括号序列,但\")(\"、\"()(”和“)))”不是。"}},{"title":"Input","value":{"format":"HTML","content":"输入的第一行包含一个整数t(1≤t≤2000)——测试用例的数量。然后是t测试用例。\n测试用例的第一行包含一个整数n(2≤n≤50),是s的长度,保证n是偶数。测试用例的第二行包含由n/2个开括号和n/2个闭括号组成的字符串s。"}},{"title":"Output","value":{"format":"HTML","content":"对于每个测试用例,打印从s中获取正则括号序列所需的最小移动次数的答案。"}},{"title":"Example","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e4\n2\n)(\n4\n()()\n8\n())()()(\n10\n)))((((())\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e1\n0\n1\n3\n\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"在示例的第一个测试用例中,将第一个括号移动到字符串的末尾就足够了。\u003cbr\u003e\n在该示例的第三个测试用例中,将最后一个括号移动到字符串的开头就足够了。\u003cbr\u003e\n在本例的第四个测试用例中,我们可以选择最后三个开括号,将它们移动到字符串的开头,并获得\"((())(())\"。"}}]}