1.5 Multiples ka khel
(RankList for this Question)
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.

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.

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.