{"trustable":true,"prependHtml":"\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 async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eSillyDarkGK has two type of numbers:\u003cbr\u003etype1. 2^x. (2, 4, 8, 16, …)\u003cbr\u003etype2. -(2^x). (-2, -4, -8, -16, …)\u003cbr\u003eHe wants a new number S, for getting S, he should choose some numbers that the sum of them is S.\u003cbr\u003eFor example, if SillyDarkGK wants 5, he can use 2, 2, -1, -1, -1, 8 and -4 to get it. (He can use number arbitrary times.)\u003cbr\u003e(S is very big, so we will give you a 01-string to describe it.)\u003cbr\u003eChoosing is boring, so SillyDarkGK wants to choose numbers as fewer as possible. To increase the difficulty, SillyDarkGK can’t use some special numbers.\u003cbr\u003e(We will also give you two 01-string to describe what you can’t use.)\u003cbr\u003eit’s guaranted that there is at least one way to solve it and answer won’t exceed\u003cbr\u003e1e9.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"Multiple query.\u003cbr\u003eOn the first line, there is a positive integer T, which describe the number of data. Next there are T groups of data.\u003cbr\u003efor each group, the first line have a positive integer n which describe the number of bits of S.\u003cbr\u003eand on the second line there is an n-length-01-string to describe S, from low to high. On the third line there is an n-length-01-string which describe the type1 number that you can’t use, from low to high, if there is a ’1’ on the x-th digit, you can’t use two\u003cbr\u003eto the power of x.\u003cbr\u003eOn the last line there is an n-length-01-string which describe the type2 number that you can’t use, from low to high, if there is a ’1’ on the x-th digit, you can’t use minus two to the power of x.\u003cbr\u003eThere is a blank line before each groups of data.\u003cbr\u003eT\u0026lt;\u003d1000, n\u0026lt;\u003d100000, sum of n\u0026lt;\u003d1000000, answer won’t exceed 1e9"}},{"title":"Output","value":{"format":"HTML","content":"Your output should include T lines, for each line, output the answer for the corre- sponding datum."}},{"title":"Sample","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\u003e3\r\n6\r\n110010\r\n110101\r\n011111\r\n9\r\n100101110\r\n011111111\r\n111111111\r\n5\r\n11111\r\n00000\r\n00000\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n233\r\n2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003efor the first datum, SillyDarkGK will use 4, 16 and -1;\u003cbr\u003efor the second datum, SillyDarkGK will use 1 for 233 times; for the third datum, SillyDarkGK will use 32 and -1.\u003cbr\u003e"}}]}