C. Removing Smallest Multiplestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a set S, which contains the first n positive integers: 1, 2, \ldots, n.You can perform the following operation on S any number of times (possibly zero):   Choose a positive integer k where 1 \le k \le n, such that there exists a multiple of k in S. Then, delete the smallest multiple of k from S. This operation requires a cost of k. You are given a set T, which is a subset of S. Find the minimum possible total cost of operations such that S would be transformed into T. We can show that such a transformation is always possible.InputThe first line of the input contains a single integer t (1 \le t \le 10\,000) — the number of test cases. The description of the test cases follows.The first line contains a single positive integer n (1 \le n \le 10^6).The second line of each test case contains a binary string of length n, describing the set T. The i-th character of the string is '1' if and only if i is an element of T, and '0' otherwise.It is guaranteed that the sum of n over all test cases does not exceed 10^6. OutputFor each test case, output one non-negative integer — the minimum possible total cost of operations such that S would be transformed into T.ExampleInput
6611111171101001400004001081001010115110011100101100Output
0
11
4
4
17
60
NoteIn the first test case, we shall not perform any operations as S is already equal to T, which is the set \{1, 2, 3, 4, 5, 6\}.In the second test case, initially, S = \{1, 2, 3, 4, 5, 6, 7\}, and T = \{1, 2, 4, 7\}. We shall perform the following operations:   Choose k=3, then delete 3 from S.  Choose k=3, then delete 6 from S.  Choose k=5, then delete 5 from S. The total cost is 3+3+5 = 11. It can be shown that this is the smallest cost possible.In the third test case, initially, S = \{1, 2, 3, 4\} and T = \{\} (empty set). We shall perform 4 operations of k=1 to delete 1, 2, 3, and 4.In the fourth test case, initially, S = \{1, 2, 3, 4\} and T = \{3\}. We shall perform two operations with k=1 to delete 1 and 2, then perform one operation with k=2 to delete 4.
6611111171101001400004001081001010115110011100101100
0 11 4 4 17 60 
['greedy', 'math', '*1200']