Turning Off the Lights

Bessie is trying to get some sleep, but the farm’s lights are keeping her awake. She is given two bit strings of length \(N\) (with \(2\le N\le20\)): one representing a row of lights and one representing a row of switches. In the lights string, a bit of 1 means the light is on and 0 means it is off. In the switches string, a bit of 1 means the switch is active and 0 means inactive.

A move consists of the following three steps:

1. Toggling exactly one switch: choose one position \(i\) (\(0\le i\le N-1\)) and flip its value (from 0 to 1 or from 1 to 0).
2. Toggling the lights: for every switch that is active after the toggle, flip the state of the corresponding light (on becomes off, off becomes on).
3. Cyclic rotation of switches: rotate the entire switches string to the right by one. That is, if the switch string (after step 1 and 2) is \(s_0s_1\cdots s_{N-1}\), it becomes \(s_{N-1}s_0s_1\cdots s_{N-2}\) before the next move.

Bessie faces \(T\) test cases (\(1\le T\le 2\cdot 10^5\)). For each test case, given the initial state of the lights and switches, compute the minimum number of moves required to turn all the lights off (i.e. the lights string becomes all 0’s).

Note: The time limit for this problem is 4 seconds, twice the default.

Input/Output Format: See the input and output descriptions below.

inputFormat

The first line contains an integer \(T\), the number of test cases. Each test case begins with an integer \(N\) (\(2\le N\le20\)). The next line is a bit string of length \(N\) representing the initial state of the lights (with 1 for on and 0 for off), and the following line is a bit string of length \(N\) representing the initial state of the switches (with 1 for active and 0 for inactive).

Example:

3
2
00
00
3
101
010
4
1010
0101

outputFormat

For each test case, output a single line containing the minimum number of moves required to turn off all the lights. It is guaranteed that a solution exists.

sample

1
2
00
00

0