给你一个集合 $$$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$$$ 是 $$$T$$$ 的元素时,字符串的第 $$$i$$$ 个字符为“1”,否则为“0”。
保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。
输出
对于每个测试用例,输出一个非负整数 - 使 $$$S$$$ 转换为 $$$T$$$ 的最小可能总操作成本。
示例
输入 #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$$$。