C. Коллекционные фигурки
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рядом с домом Монокарпа есть магазин, в котором продаются коллекционные фигурки. Скоро выйдет новый набор фигурок; в этом наборе содержится $$$n$$$ фигурок, $$$i$$$-я фигурка стоит $$$i$$$ монет и доступна для покупки с $$$i$$$-го дня по $$$n$$$-й день.

Для каждого из следующих $$$n$$$ дней Монокарп знает, может ли он посетить магазин в этот день.

Каждый раз, когда Монокарп посещает магазин, он может купить любое количество фигурок, которые продаются в магазине (конечно, он не может купить фигурку, которая еще не доступна для покупки). Если Монокарп покупает хотя бы две фигурки в один день, он получает скидку, равную стоимости самой дорогой фигурки, которую он покупает (другими словами, он получает самую дорогую из фигурок, которые он покупает, бесплатно).

Монокарп хочет купить ровно одну $$$1$$$-ю фигурку, одну $$$2$$$-ю фигурку, ..., одну $$$n$$$-ю фигурку из набора. Он не может купить одну и ту же фигурку дважды. Какова минимальная сумма денег, которую он должен потратить?

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из двух строк:

  • первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 4 \cdot 10^5$$$) — количество фигурок в наборе (и количество дней);
  • вторая строка содержит строку $$$s$$$ ($$$|s| = n$$$, каждый $$$s_i$$$ равен либо 0, либо 1). Если Монокарп может посетить магазин в $$$i$$$-й день, то $$$s_i$$$ равно 1; в противном случае $$$s_i$$$ равно 0.

Дополнительные ограничения на входные данные:

  • в каждом наборе входных данных $$$s_n$$$ равно 1, так что Монокарп всегда сможет купить все фигурки в $$$n$$$-й день;
  • сумма $$$n$$$ по всем наборам входных данных не превышает $$$4 \cdot 10^5$$$.
Выходные данные

Для каждого набора входных данных выведите одно целое число — минимальную сумму денег, которую Монокарп должен потратить.

Пример
Входные данные
4
1
1
6
101101
7
1110001
5
11111
Выходные данные
1
8
18
6
Примечание

В первом наборе входных данных Монокарп покупает $$$1$$$-ю фигурку в $$$1$$$-й день и тратит $$$1$$$ монету.

Во втором наборе входных данных Монокарп может купить $$$1$$$-ю и $$$3$$$-ю фигурки в $$$3$$$-й день, $$$2$$$-ю и $$$4$$$-ю фигурки в $$$4$$$-й день, а также $$$5$$$-ю и $$$6$$$-ю фигурки в $$$6$$$-й день. Тогда он потратит $$$1+2+5=8$$$ монет.

В третьем наборе входных данных Монокарп может купить $$$2$$$-ю и $$$3$$$-ю фигурки в $$$3$$$-й день, а все остальные фигурки в $$$7$$$-й день. Тогда он потратит $$$1+2+4+5+6 = 18$$$ монет.