移除最小倍数

题目描述

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

你可以对集合 $S$ 执行以下操作任意次数（也可能是零次）：

• 选择一个正整数 $k$，满足 $1 \le k \le n$，并且在集合 $S$ 中存在 $k$ 的一个倍数。然后，从集合 $S$ 中删除 $k$ 的最小倍数。这个操作需要 $k$ 的代价。

给你一个集合 $T$，它是集合 $S$ 的一个子集。找出将 $S$ 变为 $T$ 所需要的操作的最低总代价。我们可以证明这样的变化总是可能的。

输入格式

输入的第一行包含一个单独的整数 $t$（$1 \le t \le 10\,000$）—— 测试用例数量。然后是测试用例的描述。

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

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串，描述集合 $T$。字符串的第 $i$ 个字符如果为 '1'，则表示数字 $i$ 是集合 $T$ 的元素，如果为 '0'，则表示否。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出一个非负整数 —— 将 $S$ 变为 $T$ 所需要的操作的最低总代价。

样例 #1

样例输入 #1

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

样例输出 #1

0
11
4
4
17
60

提示

在第一个测试用例中，我们不需要执行任何操作，因为 $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 = \{\}$（空集）。我们将执行 $k=1$ 的 $4$ 次操作来删除 $1$、$2$、$3$ 和 $4$。

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