Removing Smallest Multiples

给定一个集合 $S$，其中包含 $1-n$ 这 $n$ 个数，再给定一个集合 $T$。你可以进行多次操作来将 $S$ 变成 $T$，一次操作可以选择一个正整数 $k$ 并将最小的满足是 $k$ 的倍数并且在集合 $S$ 中的元素删除，删除的代价为 $k$。问将 $S$ 变为 $T$ 的最小代价。

You 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.

The 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 $ .

For each test case, output one non-negative integer — the minimum possible total cost of operations such that $ S $ would be transformed into $ T $ .

6
6
111111
7
1101001
4
0000
4
0010
8
10010101
15
110011100101100

0
11
4
4
17
60

In 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: 1. Choose $ k=3 $ , then delete $ 3 $ from $ S $ . 2. Choose $ k=3 $ , then delete $ 6 $ from $ S $ . 3. 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 $ .