Problem

Chef has a kitchen with a bulb and $N$ switches. The bulb will only light up if the $N$ switches are in a specific order, as given by a binary string $S$ of size $N$.
In this binary string, 0 at the ��ℎith position represents that the ��ℎith switch is OFF, and 1 means that the switch is ON.

Initially, Chef has the switches in the state represented by the binary string $T$ of length $N$.

Chef can light up the bulb by performing the given operation exactly two times. The operation is defined as follows:

• Choose a substring $T[l,r]$ where $1\le l\le r\le N$, and flip all characters in the string. Note that you flip a 0 to 1 and 1 to 0.

A sequence of two operations �[�1,�2]T[a1​,a2​] and �[�3,�4]T[a3​,a4​] is considered different from a sequence of operations �[�1,�2]T[b1​,b2​] and �[�3,�4]T[b3​,b4​] if there exists a $k$ such that ��≠��ak​=bk​, where $(1\le k\le 4)$.

Your task is to find the number of ways Chef can perform these two operations to light up the bulb.

Input Format

• The first line of input will contain a single integer $T$, which denotes the number of test cases.
• Each test case consists of multiple lines of input:
  • The first line of each test case contains a space-separated integer $N$, representing the number of switches.
  • The following two lines contain binary strings, $S$ and $T$, representing the required and initial switch arrangements, respectively.

Output Format

For each test case, output on a new line, the number of ways Chef can perform these two operations to light up the bulb.

Constraints

Sample 1:

2
4
0111
1010
3
010
111

6
6

Explanation:

Test case $1$: To light the bulb, the required arrangement for bulbs needs to be 0111. The initial arrangement of switches is 1010. There are $6$ ways to light the bulb:

• Choose substring $[1,2]$, making $S=0110$ and then substring $[4,4]$, making $S=0111$.
• Choose substring $[4,4]$, making $S=1011$ and then substring $[1,2]$, making $S=0111$.
• Choose substring $[1,3]$, making $S=0100$ and then substring $[3,4]$, making $S=0111$.
• Choose substring $[3,4]$, making $S=1001$ and then substring $[1,3]$, making $S=0111$.
• Choose substring $[3,3]$, making $S=1000$ and then substring $[1,4]$, making $S=0111$.
• Choose substring $[1,4]$, making $S=0101$ and then substring $[3,3]$, making $S=0111$.