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

## 输入输出格式

### 输入格式

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

## 输入输出样例

### 输入样例 #1

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

### 输出样例 #1

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