1.5 Multiples ka khel

Score: 15pts

Time Limit: 3.00 sec

Imagine you have a set ๐ that consists of the initial ๐ positive integers: 1, 2, ..., ๐.

You have the flexibility to perform the following action as many times as needed (even zero times):

1. Choose a positive integer ๐ where 1 โค ๐ โค ๐ and there exists a multiple of ๐ within the set ๐.

2. Remove the smallest multiple of ๐ from ๐. This operation comes with a cost of ๐.

You are given a set ๐ which is a subset of ๐. Find the minimum possible total cost of operations such that ๐ would be transformed into ๐

. We can show that such a transformation is always possible.

You have the flexibility to perform the following action as many times as needed (even zero times):

1. Choose a positive integer ๐ where 1 โค ๐ โค ๐ and there exists a multiple of ๐ within the set ๐.

2. Remove the smallest multiple of ๐ from ๐. This operation comes with a cost of ๐.

You are given a set ๐ which is a subset of ๐. Find the minimum possible total cost of operations such that ๐ would be transformed into ๐

. We can show that such a transformation is always possible.

Constraints

Constraints are provided in input format

Input Format

You are given an integer ๐ก (1โค๐กโค10000), which represents the number of test cases. For each test case, the following information is given:

- An integer ๐ (1โค๐โค10^6), which represents the length of a binary string.

- A binary string of length ๐, where the ๐-th character is '1' if ๐ is an element of set ๐, and '0' otherwise.

It is guaranteed that the sum of all ๐ values across all test cases will not exceed 10^6.

- An integer ๐ (1โค๐โค10^6), which represents the length of a binary string.

- A binary string of length ๐, where the ๐-th character is '1' if ๐ is an element of set ๐, and '0' otherwise.

It is guaranteed that the sum of all ๐ values across all test cases will not exceed 10^6.

Output Format

For each test case, you need to provide a single non-negative integer as output. This integer represents the minimum total cost of operations required to transform string ๐ into string ๐, following the given conditions.

Example 1

Input:

6

6

111111

7

1101001

4

0000

4

0010

8

10010101

15

110011100101100

Output:

0

11

4

4

17

60

Explanation:

Let's delve into the test cases:

First Test Case: S and T already match with {1, 2, 3, 4, 5, 6}.

Second Test Case: Starting with S = {1, 2, 3, 4, 5, 6, 7} and T = {1, 2, 4, 7}. Our approach:

- k = 3, remove 3 from S.

- k = 3, remove 6 from S.

- k = 5, remove 5 from S.

Total cost: 11.

Third Test Case: S = {1, 2, 3, 4} and T = {}. Our method:

- Four operations with k = 1, remove 1, 2, 3, and 4.

Fourth Test Case: For S = {1, 2, 3, 4} and T = {3}, we proceed like this:

- Two operations with k = 1, remove 1 and 2.

- One operation with k = 2, remove 4.

6

6

111111

7

1101001

4

0000

4

0010

8

10010101

15

110011100101100

Output:

0

11

4

4

17

60

Explanation:

Let's delve into the test cases:

First Test Case: S and T already match with {1, 2, 3, 4, 5, 6}.

Second Test Case: Starting with S = {1, 2, 3, 4, 5, 6, 7} and T = {1, 2, 4, 7}. Our approach:

- k = 3, remove 3 from S.

- k = 3, remove 6 from S.

- k = 5, remove 5 from S.

Total cost: 11.

Third Test Case: S = {1, 2, 3, 4} and T = {}. Our method:

- Four operations with k = 1, remove 1, 2, 3, and 4.

Fourth Test Case: For S = {1, 2, 3, 4} and T = {3}, we proceed like this:

- Two operations with k = 1, remove 1 and 2.

- One operation with k = 2, remove 4.