Problem K. Pow2

SillyDarkGK has two type of numbers:
type1. 2^x. (2, 4, 8, 16, …)
type2. -(2^x). (-2, -4, -8, -16, …)
He wants a new number S, for getting S, he should choose some numbers that the sum of them is S.
For 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.)
(S is very big, so we will give you a 01-string to describe it.)
Choosing is boring, so SillyDarkGK wants to choose numbers as fewer as possible. To increase the difficulty, SillyDarkGK can’t use some special numbers.
(We will also give you two 01-string to describe what you can’t use.)
it’s guaranted that there is at least one way to solve it and answer won’t exceed
1e9.

Multiple query.
On the first line, there is a positive integer T, which describe the number of data. Next there are T groups of data.
for each group, the first line have a positive integer n which describe the number of bits of S.
and 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
to the power of x.
On 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.
There is a blank line before each groups of data.
T<=1000, n<=100000, sum of n<=1000000, answer won’t exceed 1e9

Your output should include T lines, for each line, output the answer for the corre- sponding datum.

3
6
110010
110101
011111
9
100101110
011111111
111111111
5
11111
00000
00000

3
233
2

for the first datum, SillyDarkGK will use 4, 16 and -1;
for the second datum, SillyDarkGK will use 1 for 233 times; for the third datum, SillyDarkGK will use 32 and -1.

2018 Multi-University Training Contest 10