November 30, 2023
Latest:
CodeChef Solution

# Light The Bulb CodeChef Solution ## Problem

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

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

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

• Choose a substring �[�,�] where 1≤�≤�≤�, 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] and �[�3,�4] is considered different from a sequence of operations �[�1,�2] and �[�3,�4] if there exists a  such that ��≠��, where (1≤�≤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 , 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 , representing the number of switches.
• The following two lines contain binary strings,  and , 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

• 1≤�≤2⋅105
• 1≤�≤106
•  and  consist of 0 and 1 only.
• The sum of  across all test cases won’t exceed 106.

### Sample 1:

Input

Output

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 �=0110 and then substring [4,4], making �=0111.
• Choose substring [4,4], making �=1011 and then substring [1,2], making �=0111.
• Choose substring [1,3], making �=0100 and then substring [3,4], making �=0111.
• Choose substring [3,4], making �=1001 and then substring [1,3], making �=0111.
• Choose substring [3,3], making �=1000 and then substring [1,4], making �=0111.
• Choose substring [1,4], making �=0101 and then substring [3,3], making �=0111. 