Description

Little A is studying some problems about digit statistics. One day he came across the following problem:

Represent every integer in [L..R] as an M-bit binary number (leading zeros are allowed). Now apply the following transformation to each number:

Starting from the two least significant bits, if both bits are 0, then set X = 1; otherwise set X = 0. Delete these two bits, then place X in the least significant position. Repeat this transformation until the number has only one bit left.

For example, the transformation process of 01001 is: 01001-->0100-->011-->00-->1.

Now the question is: among all transformed numbers, how many are equal to Y (Y is 0 or 1)?

Little A does not know how to solve it and asks you for help.

Input Format

The input contains multiple test cases.

The first line contains an integer T, the number of test cases.

Each of the next T sections corresponds to one test case, in the following format:

• The first line contains two integers M and Y.
• The second line contains two M-bit binary numbers L and R.

Output Format

For each test case, output one line containing a binary number, which is the count of integers in [L..R] whose transformed value equals Y. This binary number must not contain leading zeros.

1
3 1
001 101

11

Hint

• For 20% of the testdata: 1 ≤ M ≤ 16.
• For 40% of the testdata: 1 ≤ M ≤ 32.
• For 100% of the testdata: 1 ≤ M ≤ 200, 1 ≤ T ≤ 50.

Translated by ChatGPT 5