{"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":"You are given a string s consisting only of \u0027(\u0027 and \u0027)\u0027.\nThe length of s is even (has the ability to be divided by 2) and the number of \u0027(\u0027 equals the number of \u0027)\u0027 in s.\n\u003cbr\u003e\u003cbr\u003e\nIn one operation, You can select one element from the string and either move it to the beginning or to the end of the string (i.e. You choose an index i and remove s[i] from the string, \nthen either insert it in the beginning or the end of the string).\n\u003cbr\u003e\u003cbr\u003e\nYou are to tell the minimum number of operations needed to obtain a Mad sequence from s. \n\u003cbr\u003eIt is guaranteed that the answer always exists.\n\u003cbr\u003e\u003cbr\u003e\nRecall what the Mad sequence is:\n\u003cbr\u003e•\"()\" is a Mad sequence.\n\u003cbr\u003e• If s is Mad, then \"(\"+s+\")\" is also Mad.\n\u003cbr\u003e•If s and y are Mad sequences, then y+s is a Mad sequence.\n\u003cbr\u003e\n\u003cbr\u003eFor example \"(())\", \"()()\", \"(())()\"and \"()\" are Mad sequences, in the other hand \")(\", \"())\", \"()((\" and \"(((\" are not.\n\n"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input contains one integer t (1 ≤ t ≤ 2000) — the number of test cases. Then t test cases follow. \u003cbr\u003e\nEach test case contains 2 lines :\u003cbr\u003eThe first line contains one integer n (2 ≤ n ≤ 50) the length of s (it is guaranteed that it divisible by 2).\n\u003cbr\u003eThe second line contains the string s.\n"}},{"title":"Output","value":{"format":"HTML","content":"For each test case you are to print the minimum number of operations needed to obtain a Mad sequence from s.\n"}},{"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\u003e4\n2\n)(\n4\n()()\n8\n())()()(\n10\n)))((((())\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n0\n1\n3\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":"In the 1st test case : You can move the first character to the the end of the string.\n\u003cbr\u003e\u003cbr\u003e\nIn the 2nd test case : the string is already Mad so there is no need to perform any operation.\n\u003cbr\u003e\u003cbr\u003e\nIn the 3rd test case : One possible way to make the string Mad is to move the third character to the end of the string. \n\u003cbr\u003e\u003cbr\u003e\nIn the 4th test case : One possible way to make it Mad is to choose the first three characters, move them to the end of the string and obtain \"((((()))))\"."}}]}