C. Удаление наименьшего кратного
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть множество $$$S$$$, состоящее из $$$n$$$ наименьших положительных целых чисел: $$$1, 2, \ldots, n$$$.

Вы можете выполнить следующую операцию на $$$S$$$ несколько раз (возможно, ноль):

  • Выберите положительное целое число $$$k$$$ такое, что $$$1 \le k \le n$$$, и в множестве $$$S$$$ есть хотя бы одно число, кратное $$$k$$$. Затем удалите наименьшее кратное $$$k$$$ число из $$$S$$$. Стоимость такой операции равна $$$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$$$.

Пример
Входные данные
6
6
111111
7
1101001
4
0000
4
0010
8
10010101
15
110011100101100
Выходные данные
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$$$, удалите $$$3$$$ из $$$S$$$.
  2. Выберите $$$k=3$$$, удалите $$$6$$$ из $$$S$$$.
  3. Выберите $$$k=5$$$, удалите $$$5$$$ из $$$S$$$.

Общая стоимость равна $$$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$$$.