CF1734C.Removing Smallest Multiples

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.

给你一个集合 $S$，其中包含前 $n$ 个正整数：$1, 2, \ldots, n$。

你可以对 $S$ 执行以下操作任意多次（也可以不执行）：

• 选择一个满足 $1 \le k \le n$ 的正整数 $k$，使得 $S$ 中存在 $k$ 的倍数；然后，从 $S$ 中删除最小的 $k$ 的倍数。该操作的代价为 $k$。

再给你一个集合 $T$，它是 $S$ 的一个子集。求将 $S$ 变换为 $T$ 所需的最小总代价。可以证明，这样的变换总是可行的。

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

输入的第一行包含一个整数 $t$（$1 \le t \le 10\,000$），表示测试用例的数量。随后是各测试用例的描述。

每组测试用例的第一行包含一个正整数 $n$（$1 \le n \le 10^6$）。

每组测试用例的第二行包含一个长度为 $n$ 的二进制字符串，用于描述集合 $T$。该字符串的第 $i$ 个字符为 '1' 当且仅当 $i \in T$；否则为 '0'。

保证所有测试用例的 $n$ 值之和不超过 $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$.

对于每个测试用例，输出一个非负整数——使得字符串 $S$ 被转换为字符串 $T$ 所需操作的最小总代价。

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

在第一个测试用例中，我们无需执行任何操作，因为 $S$ 已经等于 $T$，即集合 ${1, 2, 3, 4, 5, 6}$。

在第二个测试用例中，初始时 $S = {1, 2, 3, 4, 5, 6, 7}$，而 $T = {1, 2, 4, 7}$。我们将执行以下操作：

1. 选择 $k=3$，然后从 $S$ 中删除 $3$。
2. 选择 $k=3$，然后从 $S$ 中删除 $6$。
3. 选择 $k=5$，然后从 $S$ 中删除 $5$。

总代价为 $3+3+5 = 11$。可以证明这是可能的最小代价。

在第三个测试用例中，初始时 $S = {1, 2, 3, 4}$，而 $T = {}$（空集）。我们将执行 $4$ 次 $k=1$ 的操作，依次删除 $1$、$2$、$3$ 和 $4$。

在第四个测试用例中，初始时 $S = {1, 2, 3, 4}$，而 $T = {3}$。我们将先执行两次 $k=1$ 的操作，删除 $1$ 和 $2$；然后执行一次 $k=2$ 的操作，删除 $4$。