M has two strings $s_1$ and $s_2$ of length $n$ consisting of characters from $\{0, 1\}$.

M wants to maximize the number of positions where the two strings have the same character, i.e., to maximize the number of indices $i$ ($1 \le i \le n$) such that $s_{1,i} = s_{2,i}$. To achieve this, M has a string editing tool. The basic operation provided by this tool is to swap two adjacent characters in a string. To maintain the distinguishability of the strings, it is stipulated that some characters in the two strings cannot participate in swaps. M can use the tool to perform any number of swaps on $s_1$ and $s_2$, where characters that are allowed to participate in swaps can be swapped any number of times.

Now, M wants to know the maximum number of positions where the two strings have the same character after using the editing tool.

Input

The input is read from the file edit.in.

This problem contains multiple test cases. The first line contains an integer $T$, representing the number of test cases. The following contains $T$ test cases, and the format for each test case is as follows:

• The first line contains an integer $n$, representing the length of the strings.
• The second line contains a string $s_1$ of length $n$ consisting of characters from $\{0, 1\}$.
• The third line contains a string $s_2$ of length $n$ consisting of characters from $\{0, 1\}$.
• The fourth line contains a string $t_1$ of length $n$ consisting of characters from $\{0, 1\}$, where $t_{1,i} = 1$ means $s_{1,i}$ can participate in swaps, and $t_{1,i} = 0$ means $s_{1,i}$ cannot participate in swaps.
• The fifth line contains a string $t_2$ of length $n$ consisting of characters from $\{0, 1\}$, where $t_{2,i} = 1$ means $s_{2,i}$ can participate in swaps, and $t_{2,i} = 0$ means $s_{2,i}$ cannot participate in swaps.

Output

Output to the file edit.out. For each test case, output a single line containing an integer representing the corresponding answer.

Examples

Input 1

1
6
011101
111010
111010
101101

Output 1

4

Note

Initially, $s_1 = 011101$, where the 4th and 6th characters cannot participate in swaps; $s_2 = 111010$, where the 2nd and 5th characters cannot participate in swaps.

Consider the following operations: first swap $s_{1,1}$ and $s_{1,2}$ to get $s_1 = 101101$, then swap $s_{1,2}$ and $s_{1,3}$ to get $s_1 = 110101$, and finally swap $s_{2,3}$ and $s_{2,4}$ to get $s_2 = 110110$. At this point, the characters at the first 4 positions of $s_1$ and $s_2$ are identical. It can be proven that no better solution exists, so output 4.

Examples 2

See edit/edit2.in and edit/edit2.ans in the contestant directory. This example contains 10 test cases, where the $i$-th ($1 \le i \le 10$) test case satisfies the constraints of test point $2i - 1$ described in the data range.