{"trustable":true,"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\u003eNikolay lives in a two-storied house. There are $$$n$$$ rooms on each floor, arranged in a row and numbered from one from left to right. So each room can be represented by the number of the floor and the number of the room on this floor (room number is an integer between $$$1$$$ and $$$n$$$). \u003c/p\u003e\u003cp\u003eIf Nikolay is currently in some room, he can move to any of the neighbouring rooms (if they exist). Rooms with numbers $$$i$$$ and $$$i+1$$$ on each floor are neighbouring, for all $$$1 \\leq i \\leq n - 1$$$. There may also be staircases that connect two rooms from different floors having the same numbers. If there is a staircase connecting the room $$$x$$$ on the first floor and the room $$$x$$$ on the second floor, then Nikolay can use it to move from one room to another.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/ecb0ea694da8b2385f60b5b08ad37eee?v\u003d1715600254\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003cspan class\u003d\"tex-font-size-small\"\u003e The picture illustrates a house with $$$n \u003d 4$$$. There is a staircase between the room $$$2$$$ on the first floor and the room $$$2$$$ on the second floor, and another staircase between the room $$$4$$$ on the first floor and the room $$$4$$$ on the second floor. The arrows denote possible directions in which Nikolay can move. The picture corresponds to the string \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e0101\u003c/span\u003e\" in the input. \u003c/span\u003e\u003c/center\u003e \u003cp\u003eNikolay wants to move through some rooms in his house. To do this, he firstly chooses any room where he starts. Then Nikolay moves between rooms according to the aforementioned rules. Nikolay never visits the same room twice (he won\u0027t enter a room where he has already been). \u003c/p\u003e\u003cp\u003eCalculate the maximum number of rooms Nikolay can visit during his tour, if:\u003c/p\u003e\u003cul\u003e \u003cli\u003e he can start \u003cspan class\u003d\"tex-font-style-bf\"\u003ein any room on any floor of his choice\u003c/span\u003e, \u003c/li\u003e\u003cli\u003e and \u003cspan class\u003d\"tex-font-style-bf\"\u003ehe won\u0027t visit the same room twice\u003c/span\u003e. \u003c/li\u003e\u003c/ul\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains one integer $$$t$$$ ($$$1 \\le t \\le 100$$$) — the number of test cases in the input. Then test cases follow. Each test case consists of two lines.\u003c/p\u003e\u003cp\u003eThe first line contains one integer $$$n$$$ $$$(1 \\le n \\le 1\\,000)$$$ — the number of rooms on each floor.\u003c/p\u003e\u003cp\u003eThe second line contains one string consisting of $$$n$$$ characters, each character is either a \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003e0\u003c/span\u003e\u0027 or a \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003e1\u003c/span\u003e\u0027. If the $$$i$$$-th character is a \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003e1\u003c/span\u003e\u0027, then there is a staircase between the room $$$i$$$ on the first floor and the room $$$i$$$ on the second floor. If the $$$i$$$-th character is a \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003e0\u003c/span\u003e\u0027, then there is no staircase between the room $$$i$$$ on the first floor and the room $$$i$$$ on the second floor.\u003c/p\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eIn hacks\u003c/span\u003e it is allowed to use only one test case in the input, so $$$t \u003d 1$$$ should be satisfied.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case print one integer — the maximum number of rooms Nikolay can visit during his tour, if he can start in any room on any floor, and he won\u0027t visit the same room twice.\u003c/p\u003e"}},{"title":"Examples","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\n5\n00100\n8\n00000000\n5\n11111\n3\n110\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n8\n10\n6\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 Nikolay may start in the first room of the first floor. Then he moves to the second room on the first floor, and then — to the third room on the first floor. Then he uses a staircase to get to the third room on the second floor. Then he goes to the fourth room on the second floor, and then — to the fifth room on the second floor. So, Nikolay visits $$$6$$$ rooms.\u003c/p\u003e\u003cp\u003eThere are no staircases in the second test case, so Nikolay can only visit all rooms on the same floor (if he starts in the leftmost or in the rightmost room).\u003c/p\u003e\u003cp\u003eIn the third test case it is possible to visit all rooms: first floor, first room $$$\\rightarrow$$$ second floor, first room $$$\\rightarrow$$$ second floor, second room $$$\\rightarrow$$$ first floor, second room $$$\\rightarrow$$$ first floor, third room $$$\\rightarrow$$$ second floor, third room $$$\\rightarrow$$$ second floor, fourth room $$$\\rightarrow$$$ first floor, fourth room $$$\\rightarrow$$$ first floor, fifth room $$$\\rightarrow$$$ second floor, fifth room.\u003c/p\u003e\u003cp\u003eIn the fourth test case it is also possible to visit all rooms: second floor, third room $$$\\rightarrow$$$ second floor, second room $$$\\rightarrow$$$ second floor, first room $$$\\rightarrow$$$ first floor, first room $$$\\rightarrow$$$ first floor, second room $$$\\rightarrow$$$ first floor, third room.\u003c/p\u003e"}}]}