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.